A. Attendance Points
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cayo is a very good student, but he is very tired with the semester at IME (Institute of Mirthful Excellence), so he started to miss some classes on purpose. Although last year things went very well this way, this year Colonel Dolphin started to straighten things out. He is very careful with class absences, so he will notice if someone does not show up.

The attendance system at IME works in a very weird way. Everyday, the students have many classes, and it is a looooong and exhausting day. Every class has a number of points $$$a_i$$$, called attendance points, and for every class a student attends, he earns $$$a_i$$$ points. At the end of the day, the sum of the earned points will compose your attendance points.

The students arrive at the first class, and they can leave earlier, before all classes end. Although they can not miss all the classes in one day (they have to go to IME everyday), there is a threshold of absent classes established by IME (because bad things happen, right?). Everyday Colonel Dolphin will look for missing students, checking if their attendance points are less than the threshold, $$$t_i$$$.

Cayo has to go to IME but does not want to spend her/his precious time with useless classes, so he decided to watch only the necessary to reach the threshold each day. Help him to count the attendance points he needs to have everyday and how many classes he has to watch to accomplish that.

Input

The first line contains one integer, $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — the number of classes during a day.

The next line will contain $$$n$$$ space-separated integers, $$$a_i$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — the number of attendance points from a class.

The next line contains one integer $$$m$$$ ($$$1 \le m \le 10 ^ 5$$$) — the number of days Cayo has to go to IME.

The next line will contain $$$m$$$ space-separated integers, $$$t_i$$$ ($$$1 \le t_i \le \sum_{i = 1}^n a_i$$$) — the number of the threshold for attendance points for that respective day.

Output

Output two numbers for each $$$m$$$ days — the minimum number of attendance points and the minimum number of classes needed each day.

Examples
Input
5
3 4 5 8 10
5
1 3 8 21 30
Output
3 1
3 1
12 3
30 5
30 5
Input
4
100000 8 9 3
4
100000 1000 100007 100009
Output
100000 1
100000 1
100008 2
100017 3