# Practice on Toph

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

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

Let’s consider an array `$A$`

which is initially empty. We’ll perform two types of operation on that array:

- Add an element
`$X$`

at the end of the array. - Remove the last element of the array.

Let’s define `$beauty \, \, value$`

of the array `$A$`

as the *summation* of the *maximum* and the *minimum* elements of the array. For example, let’s assume at any instance the array `$A$`

is *[3, 2, 4]*. The maximum element is: `$4$`

, and the minimum element is: `$2$`

. So the beauty value of the array at that instance is `$2 + 4 = 6$`

.

At any point, if the array `$A$`

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 `$A$`

is empty, you have to ignore that operation.

There will be multiple testcases in this problem. In each case, you have to process `$N$`

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 `$X$`

, you have to add `$X$`

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 `$A$`

. So, you will have `$N$`

`$beauty \, \, values$`

. You have to find the `$XOR$`

(Exclusive OR) of all the `$beauty \, \, values$`

.

**Note:** `$XOR$`

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 starts with an integer `$T$`

, the number of testcases.

The first line of each testcase will contain an integer `$N$`

, the number of operations. Instead of description of `$N$`

operations, the next line will contain 4 integers, `$a$`

, `$b$`

, `$c$`

and `$m$`

. You have to use following formula to generate some integers `$ V_i$`

, which is necessary to find the type of i^{th} operation and the value to insert if the operation is of type 1.

`$\displaystyle V_i = a \times V_{i-1} + c \pmod m $`

, where, `$ V_0 = b$`

If `$ V_i$`

is odd, then you have to add `$V_i$`

at the end of the array, i.e. `$ X = V_i$`

.

If `$ V_i$`

is even, then the operation is of type 2, you have to erase the last element of the array.

`$1 \leq T \leq 10$`

`$1 \leq a, b, c, m \leq 10^8$`

`$1 \leq N \leq 10^3$`

`$1 \leq N \leq 10^6$`

`$1 \leq N \leq 10^7$`

For each testcase, print the `$XOR$`

of the `$beauty \, \, values$`

of the array after performing each operation.

Input | Output |
---|---|

1 9 1 2 3 7 | 12 |

**Explanation of the testcase 1:**

Initially, *V _{0} = 2*.
By using equation

XOR of all the beauty values of the array after performing each operation is

Hence, the answer of testcase 1 is

55% Solution Ratio

Samin_SieyamEarliest,

iamSadeeFastest, 0.9s

YouKnowWhoLightest, 78 MB

NirjhorShortest, 594B

Login to submit