Easy Peasy, Lemon Squeezy

moshiur_cse15 NHSPC 2020 Practice
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 beauty 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][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 0 i.e. the beauty value is 0 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 beauty value of the array AA. So, you will have NN beauty values. You have to find the XORXOR (Exclusive OR) of all the beauty values.

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 (1T101 \leq T \leq 10), the number of testcases.

The first line of each testcase will contain an integer NN (1N1071 \leq N \leq 10^7), the number of operations. Instead of description of NN operations, the next line will contain 4 integers, aa, bb, cc and mm (1a,b,c,m1081 \leq a, b, c, m \leq 10^8). You have to use following formula to generate some integers ViV_i, which is necessary to find the type of ii-th operation and the value to insert if the operation is of type 1.

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

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

Output

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

Sample

InputOutput
1
9
1 2 3 7
12

Initially, V0=2V_0 = 2. By using equation Vi=a×Vi1+c(modm)V_i = a \times V_{i - 1} + c (mod m), V1=5V_1 = 5, It's odd, 5 is added at the back of the array, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V2=1V_2 = 1, it's odd too, 1 is added at the back of the array, hence the array, A=[5,1]A = [5, 1], the beauty value of the array is 1+5=61 + 5 = 6.

V3=4V_3 = 4, it's even, the last element of the array has removed, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V4=0V_4 = 0, it's even too, the last element of the array has removed, hence the array, A=[]A = [], i.e empty, the beauty value of the array is 0+0=00 + 0 = 0.

V5=3V_5 = 3, it's odd, 3 is added at the back of the array, hence the array, A=[3]A = [3], the beauty value of the array is 3+3=63 + 3 = 6.

V6=6V_6 = 6, it's even, the last element of the array has removed, hence the array, A=[]A = [], i.e empty, the beauty value of the array is 0+0=00 + 0 = 0.

V7=2V_7 = 2, it's even too, the array is empty, hence skipped the operation, the beauty value of the array is 0+0=00 + 0 = 0.

V8=5V_8 = 5, it's odd, 5 is added at the back of the array, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V9=1V_9 = 1, it's odd too, 1 is added at the back of the array, hence the array, A=[5,1]A = [5, 1], the beauty value of the array is 1+5=61 + 5 = 6.

XORXOR of all the beauty values of the array after performing each operation is 106100600106=1210 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12. Hence, the answer of testcase 1 is 12.


Submit

Login to submit.

Statistics

54% Solution Ratio
Samin_SieyamEarliest, Jun '20
defaltFastest, 0.3s
YouKnowWhoLightest, 78 MB
NirjhorShortest, 594B
Toph uses cookies. By continuing you agree to our Cookie Policy.