#215896. [JOI Open 2015] Sterilizing Spray

Mr. JOI is working at the IOI Pharmaceutical Co., Ltd. In this company, researchers are busy with experimental work to develop new sterilization sprays.

In this company, the strength of a sterilization spray is defined as follows: when we use a spray of strength once for a culture plate with bacteria, the number of bacteria on it becomes , which is the integer obtained from by rounding off fractions. Now, a new spray of strength is developed. In order to test the performance of this spray, they plan to experiment on it. They use culture plates numbered . At the beginning, there are bacteria on the culture plate . In the experiment, they implement operations in sequence. Each operation is one of the following:

• Operation 1: Choose a culture plate and an integer , and adjust the number of bacteria on the culture plate . After this operation, the number of bacteria on the culture plate becomes .
• Operation 2: Choose two integers with . Spray once for each of the culture plates .
• Operation 3: Choose two integers with . Calculate the sum of the numbers of bacteria on the culture plates , and record it.

Mr. JOI is curious about the results of the experiment assuming that the new spray works as expected. Since you are a good programmer, he asks you to predict the results of the experiment.

Write a program which determines the numbers recorded by the operation 3s in the experiment.

Task

Given the strength of the spray and the information on the operations in the experiment, write a program which determines the numbers recorded by the operation 3s.

Read the following data from the standard input.

• The first line of input contains three space separated integers . This means the strength of the spray is , the number of culture plates is , and the number of operations in the experiment is .
• The -th line () of the following lines contains an integer . This means there are bacteria on the culture plate at the beginning of the experiment.
• The -th line () of the following lines contains three space separated integers . They indicate information on the -th operation in the experiment.
  • When , they mean the operation 1 with .
  • When , they mean the operation 2 with .
  • When , they mean the operation 3 with .

Write the numbers recorded by the operation 3s in the experiment. The number of lines in the output is equal to the number of the operation 3s implemented in the experiment.

样例输入 1

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

样例输出 1

8
3
8

样例输入 2

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

样例输出 2

174
444
76
23
41

Sample 1 Explanation

• At the beginning of the experiment, the numbers of bacteria on the culture plates are .
• Adjust the number of bacteria on the culture plate 2 to 5. After this operation, the numbers of bacteria on the culture plates are .
• The numbers of bacteria on the culture plates 3,4,5 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are .
• Since the sum of the numbers of bacteria on the culture plates 2,3,4,5 is 8, write 8 to the output.
• The numbers of bacteria on the culture plates 1,2,3,4 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are .
• Adjust the number of bacteria on the culture plate 3 to 2. After this operation, the numbers of bacteria on the culture plates are .
• Since the sum of the numbers of bacteria on the culture plates 3,4,5 is 3, write 3 to the output.
• Adjust the number of bacteria on the culture plate 2 to 4. After this operation, the numbers of bacteria on the culture plates are .
• The numbers of bacteria on the culture plates 1,2 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are .
• Adjust the number of bacteria on the culture plate 1 to 4. After this operation, the numbers of bacteria on the culture plates are .
• Since the sum of the numbers of bacteria on the culture plates 1,2,3,4,5 is 8, write 8 to the output.

Constraints

All input data satisfy the following conditions.

• .
• .
• .
• ().
• ().
• When is satisfied, and ().
• When is satisfied, ().

Subtask

Subtask 1 [5 points]

• .
• .

Subtask 2 [10 points]

• .

Subtask 3 [10 points]

• ().
• When is satisfied, ().

Subtask 4-10 [75 points]

There are no additional constraints.