2.2 Lots of mods

Score: 60pts

Time Limit: 1.00 sec

You are given three integers, \(n\), \(index\), \(m\) and two arrays of size \(n\). In the first array, you are given pointers and in the second array, you are given values. The index variable defines the starting index for the pointer array.

You maintain a variable \(answer\), which is initially \(0\). In each operation, your \(count\) is incremented by one. Initially, the \(count\) is \(0\). You take the value pointed at by the pointer[index] element from the values array and start performing operations. When \(count\)%\(4\) is \(0\) you do the addition of the \(answer\) and \(value\) mod \(m\), when \(count\)%\(4\) is \(1\), you do subtraction of \(answer\) and \(value\) mod \(m\), when \(count\)%\(4\) is \(2\), you do multiplication of \(answer\) and \(value\) mod \(m\), and when \(count\)%\(4\) is \(3\), you do division mod \(m\) of the answer and the value (ie. (\(answer \over value\)) mod \(m\)). Then you set the \(index\) to pointer[index] and increment the \(count\). You keep on doing this until you traverse the entire pointers array.

In the end, you print the value of the answer variable.

You maintain a variable \(answer\), which is initially \(0\). In each operation, your \(count\) is incremented by one. Initially, the \(count\) is \(0\). You take the value pointed at by the pointer[index] element from the values array and start performing operations. When \(count\)%\(4\) is \(0\) you do the addition of the \(answer\) and \(value\) mod \(m\), when \(count\)%\(4\) is \(1\), you do subtraction of \(answer\) and \(value\) mod \(m\), when \(count\)%\(4\) is \(2\), you do multiplication of \(answer\) and \(value\) mod \(m\), and when \(count\)%\(4\) is \(3\), you do division mod \(m\) of the answer and the value (ie. (\(answer \over value\)) mod \(m\)). Then you set the \(index\) to pointer[index] and increment the \(count\). You keep on doing this until you traverse the entire pointers array.

In the end, you print the value of the answer variable.

Constraints

\(1 \leq t \leq 10\)

\(2 \leq n \leq 10^{3}\)

\(5 \leq m \leq 10^{9} + 7\), m is prime

\(0 \leq index \lt n\)

\(0 \leq pointers[i] \lt n \)

\(1 \leq values[i] \leq 10^{3} \)

\(2 \leq n \leq 10^{3}\)

\(5 \leq m \leq 10^{9} + 7\), m is prime

\(0 \leq index \lt n\)

\(0 \leq pointers[i] \lt n \)

\(1 \leq values[i] \leq 10^{3} \)

Input Format

The first line contains an integer \(t\), which denotes the number of test cases.

Each test case contains three lines.

The first line of each test case contains three space-separated integers, \(n\), \(index\), \(m\). \(n\) represents the size of the arrays, \(index\) represents the index from which you begin the traversal of the pointers array and \(m\) represents the prime number with which you have to perform the modulo operation.

The next line contains \(n\) space-separated integers which are the elements of the pointer array.

The next line contains \(n\) space-separated integers which are the elements of the values array.

Each test case contains three lines.

The first line of each test case contains three space-separated integers, \(n\), \(index\), \(m\). \(n\) represents the size of the arrays, \(index\) represents the index from which you begin the traversal of the pointers array and \(m\) represents the prime number with which you have to perform the modulo operation.

The next line contains \(n\) space-separated integers which are the elements of the pointer array.

The next line contains \(n\) space-separated integers which are the elements of the values array.

Output Format

For each test case, print a single integer on a new line, the value of the variable answer in each test case.

Example 1

Input:

1

3 0 5

1 2 0

10 20 31

Output:

0

Explanation:

Here \(n = 3\), \(index = 0\) and \(m = 5\).

So we initialize the \(answer\) to \(0\) and the value of \(count = 0\).

Initially the value pointed will be value[pointers[index]],.Since the value of \(index\) is \(0\), the value pointed will be value[pointers[0]], which is equal to \(20\). Now since the value of \(count\) is \(0\), and \(0\)%\(4\) is \(0\), we perform the addition operation. So the answer will be \((0 + 20)\) % \(5\), which is equal to \(0\).

We update the value of the \(answer\) variable to \(0\). The value of \(count\) is updated to \(1\). The value of \(index\) will be updated to pointers[index]. So \(index\) = pointers[index]. So \(index = 1\).

Now the next value will be pointed to: values[pointers[1]] = values[2] which is \(31\). Since the value of \(count\) is \(1\) and \(count%4\) is \(1\) we perform subtraction of answer and value mod \(m\). So the resulting answer will be \((0-31)\)%\(5\), which is equal to \(4\).

The value of the \(answer\) variable will be updated to \(4\). The value of \(count\) will be updated to \(2\). The value of \(index\) will be updated to pointers[index]. So \(index\) = pointers[index]. So \(index = 2\).

The next value pointed will be: values[pointers[2]] = values[0] which is \(10\). Since the value of \(count\) is \(2\) and the \(count\)%\(4\) is \(2\), we perform a multiplication operation between \(answer\) and \(value\) mod \(m\). The result will be \(40\) % \(5\), which is equal to \(0\). We have now completed the traversal of the pointers array.

So we have our final answer which is \(0\).

1

3 0 5

1 2 0

10 20 31

Output:

0

Explanation:

Here \(n = 3\), \(index = 0\) and \(m = 5\).

So we initialize the \(answer\) to \(0\) and the value of \(count = 0\).

Initially the value pointed will be value[pointers[index]],.Since the value of \(index\) is \(0\), the value pointed will be value[pointers[0]], which is equal to \(20\). Now since the value of \(count\) is \(0\), and \(0\)%\(4\) is \(0\), we perform the addition operation. So the answer will be \((0 + 20)\) % \(5\), which is equal to \(0\).

We update the value of the \(answer\) variable to \(0\). The value of \(count\) is updated to \(1\). The value of \(index\) will be updated to pointers[index]. So \(index\) = pointers[index]. So \(index = 1\).

Now the next value will be pointed to: values[pointers[1]] = values[2] which is \(31\). Since the value of \(count\) is \(1\) and \(count%4\) is \(1\) we perform subtraction of answer and value mod \(m\). So the resulting answer will be \((0-31)\)%\(5\), which is equal to \(4\).

The value of the \(answer\) variable will be updated to \(4\). The value of \(count\) will be updated to \(2\). The value of \(index\) will be updated to pointers[index]. So \(index\) = pointers[index]. So \(index = 2\).

The next value pointed will be: values[pointers[2]] = values[0] which is \(10\). Since the value of \(count\) is \(2\) and the \(count\)%\(4\) is \(2\), we perform a multiplication operation between \(answer\) and \(value\) mod \(m\). The result will be \(40\) % \(5\), which is equal to \(0\). We have now completed the traversal of the pointers array.

So we have our final answer which is \(0\).