D. Djqifs Tijgu
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Arthur is a spy from the renowned secret agency MI-9548. In his missions, for security reasons, he uses the most sophisticated encryption algorithm to communicate with headquarters: the Shift Cipher.

The messages sent by Arthur are represented by lists containing integer values between $$$0$$$ and $$$9999$$$. The Shift Cipher consists of choosing a "shift" between $$$0$$$ and $$$9999$$$ and adding that same value to all elements of the list. If this application causes the value of an element to exceed $$$9999$$$, the remainder of the value when divided by $$$10000$$$ should be taken.

For example, if Arthur's message is $$$[1, 2, 3, 4]$$$ and we choose the shift $$$3$$$, we will have the new list $$$[4, 5, 6, 7]$$$. If we choose the shift $$$9998$$$, we will have the list $$$[9999, 0, 1, 2]$$$.

Arthur has a favorite phrase $$$B$$$, represented by a list of numbers, and he would like to choose the encryption shift in such a way that this phrase appears as many times as possible in the encrypted message.

For example, if the message to be encrypted is $$$[1, 2, 3, 1, 2]$$$ and Arthur likes the phrase $$$[6, 7]$$$, he should choose the shift $$$5$$$, as this will result in the message $$$[6, 7, 8, 6, 7]$$$, which contains Arthur's phrase twice.

Help Arthur by finding the shift that results in the highest number of occurrences of his favorite phrase in the message $$$A$$$ to be encrypted, and additionally report the number of occurrences. If more than one shift maximizes the number of occurrences, find the smallest one.

Input

The first line of input contains two integers $$$N$$$ and $$$M$$$ $$$(2 \le M \le N \le 10^6)$$$, which correspond to the length of the message $$$A$$$ and the length of the phrase $$$B$$$, respectively.

The second line contains $$$N$$$ integers separated by spaces: the message $$$A$$$ $$$(0 \le A_i \lt 10^4)$$$.

The third line contains $$$M$$$ integers separated by spaces: the phrase $$$B$$$ $$$(0 \le B_i \lt 10^4)$$$.

Output

The output should contain two numbers separated by a space: a value between $$$0$$$ and $$$9999$$$, representing the smallest shift that maximizes the occurrences of the phrase, and the number of occurrences.

Examples
Input
5 2
1 2 3 1 2
6 7
Output
5 2
Input
4 2
1 2 3 4
0 0
Output
0 0
Input
2 2
452 453
0 1
Output
9548 1