Description

Kuo-chan is given a sequence A and a constant K as his birthday present from Yang-chan.

Kuo-chan is allowed to perfrom the following operation:

1. push x — push x to the end of A
2. pop — remove the median value of A （the median value of A is A[ (|A|+1)/2 ]）
3. programming tanoshi — for 1 <= i <= |A|, assign A[ i ] % K to A[ i ]

 

For example, if A = [4, 3, 5], K = 2

push 11　►　A = [4, 3, 5, 11]

pop　►　A = [4, 5, 11]

pop　►　A = [4, 11]

programming tanoshi　►　A = [0, 1] 

 

Yang-chan is curious about what A is after Kuo-chan performs some operations to it.

Help him find it out!

Input

The first line contains three integers N K Q — the length of A, the constant Yang-chan gives Kuo-chan, the number of operations Kuo-chan performs.

The second line contains N integers a₁, a₂, ..., a_N （1 <= a_i <= N） — the elements of A. 

Each of the next Q lines describes the operations. Each line is one of three types:

1. push x （1 <= x <= N）
2. pop
3. programming tanoshi

 

Different testcases have different constraints.

1. N <= 10³, Q <=   N, K <= N, operations: {pop}
2. N <= 10³, Q <= 2N, K <= N, operations: {pop, push}
3. N <= 10³, Q <= 2N, K <= N, operations: {pop, push, programming tanoshi}
4. N <= 10⁵, Q <=   N, K <= N, operations: {pop}
5. N <= 10⁵, Q <= 2N, K <= N, operations: {pop, push}
6. N <= 10⁵, Q <= 2N, K <= N, operations: {pop, push, programming tanoshi}

Output

You should print one line containing the elements of A after the operations. For 1 <= i <= |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

13163.cpp

Partial Judge Header

13163.h

Tags

Add Tag

Discuss