PESADA05 - Binary Search the product of Large Intergers

no tags 

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


Added by:Prof. Channa Bankapur
Date:2015-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C