Midterm Madness

Points: 1

Time limit: 1.0s

Memory limit: 256M

Authors:

oree, Parsa

Problem type

Allowed languages

C, C++, Java, Python

Throughout the semester, Parsa was regularly writing notes for each unit of coursework in his programming course. On his drive, he has $n$ ~n~ PDF files, with the $i$ ~i~th PDF corresponding to the $i$ ~i~th teaching session, taught in order. Each file was saved by Parsa at the end of each unit. The sessions for the overall course are labelled $1$ ~1~ through to $n$ ~n~.

Additionally, when studying for the midterm test and final exam, Parsa used a PDF merging tool to create a master document, making it easier to study everything at once. That is, the midterm test took place between the $m$ ~m~th and the $m+1$ ~m+1~th unit (with $1\leq m \leq n-1$ ~1\leq m \leq n-1~), and Parsa merged all PDFs from $1$ ~1~ to $m$ ~m~ together.

He also merged all $n$ ~n~ files together at the end of the semester for the final exam, meaning that his drive contains $n+2$ ~n+2~ total files. However, his filesystem got messed up, so he can't tell which file is which anymore! Can you tell which file is which just by looking at their sizes? We know the sizes of all $n+2$ ~n+2~ files, and we know that merged file sizes are exactly equal to the sum of the files they were created from.

Input

The first line contains an integer $n\ (2 \leq n \leq 10^5)$ ~n\ (2 \leq n \leq 10^5)~, representing the number of course units which Parsa took notes for.

The following line contains $n+2$ ~n+2~ space-separated integers $a_i\ (1 \leq a_i \leq 10^9)$ ~a_i\ (1 \leq a_i \leq 10^9)~, representing the size of each file on his drive (all the course files in addition to the two merged files). Additionally, the properties regarding the merged files are guaranteed to hold, that is, one of the $n+2$ ~n+2~ file sizes will be the sum of $n$ ~n~ of the other files (the final exam merged file), and one of them will be the sum of $m$ ~m~ other files where $(1 \leq m \leq n-1)$ ~(1 \leq m \leq n-1)~ (the midterm merged file).

Output

Output the size of the midterm test merged file followed by the size of the merged final exam file, separated by a space.

Example

Input 1

2
11 5 6 5

Output 1

5 11

Input 2

10
50 33 21 201 356 20 11 18 79 14 15 95

Output 2

201 356

$201 = 79+50+33+18+21$ ~201 = 79+50+33+18+21~ (These are the notes from the course units that came before the midterm)
$356 = 50+33+21+20+11+18+79+14+15+95$ ~356 = 50+33+21+20+11+18+79+14+15+95~ (These are the notes from the entire course)

Comments

There are no comments at the moment.