Problem Description

You are trying to sell trading cards. Each type of card is numbered from $1$ to $N$. Initially, the stock of card $i\ (1 \leq i \leq N)$ is $C_i$ cards.

You must process the following $Q$ queries $S_1, \ldots, S_Q$ in order:

• Single sale: Sell $a$ cards of type $x$. If there is not enough stock, do nothing. Given in the format 1 x a.
• Set sale: Sell $a$ cards each of the cards with odd numbers. If any type has insufficient stock, do nothing. Given in the format 2 a.
• All types sale: Sell $a$ cards each of all types. If any type has insufficient stock, do nothing. Given in the format 3 a.

Output the total number of cards sold eventually.

Input Format

The input is given from the standard input in the following format:

$ N $ $ C_1 $ $ C_2 $ $ ... $ $ C_N $ $ Q $ $ S_1 $ $ S_2 $ $ : $ $ S_Q $

Output Format

Output the total number of cards sold eventually.

Sample Input and Output

Sample Input #1

4
5 3 3 5
6
1 2 1
2 2
2 2
3 100
3 1
1 1 3

Sample Output #1

9

Sample Input #2

10
241 310 105 738 405 490 158 92 68 20
20
2 252
1 4 36
2 69
1 5 406
3 252
1 3 8
1 10 10
3 11
1 4 703
3 1
2 350
3 10
2 62
2 3
2 274
1 2 1
3 126
1 4 702
3 6
2 174

Sample Output #2

390

Sample Input #3

2
3 4
3
1 2 9
2 4
3 4

Sample Output #3

0

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$
• $1 \leq C_i \leq 10^9$
• $1 \leq Q \leq 200,000$
• $ S_i $ is one of the following formats:
• 1 x a ($1 \leq x \leq N$ and $1 \leq a \leq 10^9$)
• 2 a ($1 \leq a \leq 10^9$)
• 3 a ($1 \leq a \leq 10^9$)
• All numbers given in the input are integers.

Sample Explanation 1

Initially, the stock of each card is $ 5,3,3,5 $. The queries are processed as follows:
1. Sell $ 1 $ card of type $ 2 $. After this query, the stock is $ 5,2,3,5 $.
2. Sell $ 2 $ cards each of types $ 1,3 $. After this query, the stock is $ 3,2,1,5 $.
3. Do nothing because the stock of card $ 3 $ is insufficient.
4. Do nothing because the stock is insufficient.
5. Sell $ 1 $ card each of all types. After this query, the stock is $ 2,1,0,4 $.
6. Do nothing because the stock is insufficient.

Thus, $ 1,4,4 $ cards are sold in queries $ 1,2,5 $, totaling $ 9 $ cards sold.

见题面 Input 部分

见题面 Output 部分