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

Discuss

Description

 

In the Cat Kingdom, cats are everywhere.

One day, the king of Cat Kingdom wanted to know how many cats there are. However, there were too many cats, so the king divided the cats into t groups and calculated the number of cats in each group separately. In this way, he was wondering if he counts every n cats, can he complete the counting through all the cats in the group?

For example:

If he counts every 3 cats, then the process will be 3, 6, 9, 12... cats. However, he will not be able to complete the counting for 25 cats because there will be 1 cat left anyway.

The king wants you to help him write a program to check if he can count n cats at a time and no cats will be left in each group. Namely, cats can be divided by n with no remainder.

Hint:

Method to check if a number is multiple of n:

For 3: Sum the digits. The result must be divisible by 3.

For 4: The last two digits form a number that is divisible by 4

For 5: The last digit is 0 or 5.

For 6: It is divisible by 2 and by 3.

(7 is not included in this problem)

For 8: The last three digits form a number that is divisible by 8.

For 9: Sum the digits. The result must be divisible by 9.

For 11: Take the alternating sum of the digits from left to right in a given number. If the sum is divisible by 11, so is the original number. For example: 2728 has an alternating sum of digits 2 – 7 + 2 – 8 = -11. Since -11 is divisible by 11, so is 2728.

 

 

Input

The first line contains an integer t, means how many group of cats should be counted.

The next t lines, each line contains two integer x, n, means the number of cats and how many cats should be counted at once.

for all testcase:

• 1 ≤ t ≤ 10
• 1 ≤ x < 10¹⁰⁰⁰⁰⁰
• 2 <= n <= 11 and n ≠ 7
• (1/10) n = 2
• (1/10) n = 3
• (2/10) 1 <= x < 10¹⁸ 

Output

The output contains t lines, for each group of cats, if there are 0 cats left in the end, output "Yes", otherwise, output "No".

Sample Input  Download

Sample Output  Download

Partial Judge Code

13166.cpp

Partial Judge Header

13166.h

Tags

Discuss