2.2 Lots of mods
(RankList for this Question)
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.

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} \)

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.

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\).

Log In to solve the Question