Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Peasy, Lemon Squeezy

By moshiur_cse15 · Limits 2s, 256 MB

Let's consider an array AA which is initially empty. We'll perform two types of operation on that array:

  1. Add an element XX at the end of the array.
  2. Remove the last element of the array.

Let's define beautyvaluebeauty \, \, value of the array AA as the summation of the maximum and the minimum elements of the array. For example, let's assume at any instance the array AA is [3, 2, 4]. The maximum element is: 44, and the minimum element is: 22. So the beauty value of the array at that instance is 2+4=62 + 4 = 6.

At any point, if the array AA becomes empty, the value of the maximum and minimum is 00 i.e. the beauty value is 00 then. At any point, if you are asked to perform the second operation (removing the last element of the array) while the array AA is empty, you have to ignore that operation.

There will be multiple testcases in this problem. In each case, you have to process NN operations. In each operation, you'll be given the type of the operation. If the type of the operation is of first kind, then you'll be given another integer XX, you have to add XX at the end of the array. If the type of the operation is of second kind, you have to remove the last element of the array. After each operation, you have to find the beautyvaluebeauty \, \, value of the array AA. So, you will have NN beautyvaluesbeauty \, \, values. You have to find the XORXOR (Exclusive OR) of all the beautyvaluesbeauty \, \, values.

Note: XORXOR is a bitwise logical operation that outputs true only when inputs differ (one is true, the other is false). The truth table for all combinations of bits has given below:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

Input

Input starts with an integer TT, the number of testcases.

The first line of each testcase will contain an integer NN, the number of operations. Instead of description of NN operations, the next line will contain 4 integers, aa, bb, cc and mm. You have to use following formula to generate some integers Vi V_i, which is necessary to find the type of ith operation and the value to insert if the operation is of type 1.

Vi=a×Vi1+c(modm)\displaystyle V_i = a \times V_{i-1} + c \pmod m , where, V0=b V_0 = b

If Vi V_i is odd, then you have to add ViV_i at the end of the array, i.e. X=Vi X = V_i.
If Vi V_i is even, then the operation is of type 2, you have to erase the last element of the array.

Constraints

1T101 \leq T \leq 10
1a,b,c,m1081 \leq a, b, c, m \leq 10^8

Subtask 1 (5 points)

1N1031 \leq N \leq 10^3

Subtask 2 (15 points)

1N1061 \leq N \leq 10^6

Subtask 3 (80 points)

1N1071 \leq N \leq 10^7

Output

For each testcase, print the XORXOR of the beautyvaluesbeauty \, \, values of the array after performing each operation.

Sample

InputOutput
1
9
1 2 3 7
12

Explanation of the testcase 1:
Initially, V0 = 2.
By using equation Vi = a ✕ Vi - 1 + c (mod m),
V1 = 5, It's odd, 5 is added at the back of the array, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V2 = 1, It's odd too, 1 is added at the back of the array, hence the array, A = [5, 1], the beauty value of the array is = 1 + 5 = 6
V3 = 4, It's even, the last element of the array has removed, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V4 = 0, It's even too, the last element of the array has removed, hence the array, A = [], i.e empty, the beauty value of the array is = 0 + 0 = 0
V5 = 3, It's odd, 3 is added at the back of the array, hence the array, A = [3], the beauty value of the array is = 3 + 3 = 6
V6 = 6, It's even, the last element of the array has removed, hence the array, A = [], i.e empty, the beauty value of the array is = 0 + 0 = 0
V7 = 2, It's even too, the array is empty, hence skipped the operation, the beauty value of the array is = 0 + 0 = 0.
V8 = 5, It's odd, 5 is added at the back of the array, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V9 = 1, It's odd too, 1 is added at the back of the array, hence the array, A = [5, 1], the beauty value of the array is = 1 + 5 = 6
XOR of all the beauty values of the array after performing each operation is = 10 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12.
Hence, the answer of testcase 1 is 12.

Discussion

Statistics


53% Solution Ratio

Samin_SieyamEarliest, Jun '20

expert_loserFastest, 0.9s

YouKnowWhoLightest, 78 MB

NirjhorShortest, 594B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.