Game with Numbers#4241
Sign in

Game with Numbers

1 second
64 megabytes
Easy

Vasya and Petya are playing a game with sequences of numbers. Each of them writes down eight numbers, denoted x_1, x_2, \dots, x_8, and there are also eight "magic" numbers: c_1, c_2, \dots, c_8. To calculate each subsequent number in the sequence, x_i (for i > 8), they use the formula:

x_i = x_{i-1} \cdot c_1 + x_{i-2} \cdot c_2 + x_{i-3} \cdot c_3 + x_{i-4} \cdot c_4 + x_{i-5} \cdot c_5 + x_{i-6} \cdot c_6 + x_{i-7} \cdot c_7 + x_{i-8} \cdot c_8

Afterwards, they take the result modulo , so that all values satisfy 0 \le x_i \le 999.

Each of Vasya and Petya has a different sequence of eight numbers. They have made a bet: whoever's sequence appears as a contiguous subsequence in the generated sequence first, wins at that moment.

For example, if Vasya's sequence is 500, 12, 0, 8, 67, 289, 901, 415, and the generated sequence contains the values x_{91} = 500, x_{92} = 12, x_{93} = 0, x_{94} = 8, x_{95} = 67, x_{96} = 289, x_{97} = 901, x_{98} = 415 in order, then Vasya wins at x_{98}. The numbers must occur in the exact given order, with no interruptions.

Vasya and Petya are tired of performing the calculations manually and ask you to write a program to determine who wins, and at which position.

Input

The input consists of four lines, each containing eight non-negative integers:

  • The first line contains the initial numbers: x_1, x_2, \dots, x_8.

  • The second line contains the magic numbers: c_1, c_2, \dots, c_8.

  • The third line contains Vasya's sequence.

  • The fourth line contains Petya's sequence.

Output

Output who wins, and at which position. For example, if Vasya wins at x_{98} (that is, his sequence matches x_{91}, x_{92}, \dots, x_{98}), output:

Vasya wins at 98.

If Petya wins at x_{98}, output:

Petya wins at 98.

You may assume that someone will win by x_{10000000} at the latest.

Examples

Example 1

Loading
Loading