Multiply two large nonnegative integers and search it in a lexicographically sorted list of a large number of large integers.

Input

The input begins with a positive integer n indicating the size of the list of large integers (1 <= n <= 1000000). It is followed by n lines having a nonnegative large integer on each line and they are listed in lexicographic order (1 <= number of digits in the large integer <= 2000). A new line has a positive integer t indicating the number of pairs of large integers. It is followed by t lines having two nonnegative large integers in each line separated by a space (1 <= number of digits in the large integer <= 1000).

Output

Output to have t lines where each line has two numbers separated by a space. First number in each line is the product of two large integers provided in the input and the other number is the 0-based index of the product in the list of n large integers provided in the earlier part of the input.

Example

Input:
10
0
1186379681736876234567001234
2345671234
30
45678923
56789143
789
78912123453245
80779853376
911234341234
5
1234 0
5 6
123456 654321
876142389164 5761523128
1186379681736876234567001234 1

Output:
0 0
30 3
80779853376 8
5047914638589562584992 -1
1186379681736876234567001234 1