D. Delivering Orders
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Iván has just embarked in his newest entrepreneurship: a charbroiled burgers stand. The unique seasoning that he uses has attracted a lot of customers, so he's figuring out new ways to expand his business.

Since he has really loyal customers he knows that each day he will receive $$$N$$$ burger orders, always being requested in the same order (sequence) as in previous days. Every order asks for certain quantities of each of the $$$K$$$ ingredients that are available in the stand. Iván can only fulfill an order if, for each ingredient, he has an available amount greater than or equal to the amount that is being requested.

To minimize costs Iván wants to start buying items in bulk, for this he will start having a large inventory for each of the $$$K$$$ ingredients. As he has bought his first batch in bulk, he would like to know how much time will they last.

Help Iván find out when will he run out of his current inventory and won't be able to fulfill another one. Hurry up, a hoard of hungry customers is waiting!

Input

On the first line, an integer $$$K - $$$ ($$$1\leq k \leq 100$$$) $$$-$$$ the number of different ingredients.

On the second line, $$$K$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 10^{12}$$$) $$$-$$$ the available quantity for the $$$i-$$$th ingredient.

On the third line, an integer $$$N - $$$ ($$$ 1 \leq N \leq 10^4 $$$) $$$-$$$ the number of orders that will arrive each day.

The following $$$N$$$ lines will have $$$K - $$$ ($$$0 \leq b_{ij} \leq 10^{12}$$$) numbers each, for the $$$i-$$$th line the $$$j-$$$th number will indicate the quantity of the ingredient of type $$$j$$$ that the $$$i$$$-th order needs. It is guaranteed that each order will need at least one ingredient.

Output

Two numbers, indicating the first day Iván can't fulfill all the orders, and the index (1 based) of the first order Iván couldn't fulfill.

Examples
Input
4
7 20 11 10
3
0 2 1 1
1 3 2 1
1 2 1 2
Output
3 3
Input
4
3 7 2 4
2
1 2 3 1
3 2 2 1
Output
1 1