405845: GYM102134 F A+B

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. A+Btime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

Like every Andrew, our Andrew likes playing with numbers and addition in columns. He has two decimal numbers X and Y. Initially, they are equal to 0. Number positions are numbered sequentially from left to right, numbering is 1-based. Andrew has the following types of operations:

  • 1 k a b - To insert the digit a (0 ≤ a ≤ 9) after the k-th digit of the number X (if k is 0, then the digit goes to the beginning of the number). Similarly insert the digit b in the number Y. It is guaranteed that at the moment of the execution of operation the numbers contain at least k digits.
  • 2 k - To delete the k-th digit from the numbers X and Y. It is guaranteed that at the moment of the execution of operation the numbers contain at least k digits.
  • 3 k - To output the k-th digit of the number Z. Z is equal to the sum of X and Y. Note that it is not guaranteed for this operation that the number Z has the k -th digit. If there is no this digit, output  - 1.

It is guaranteed that after performing each operation the numbers X and Y do not have leading zeros.

Input

The first line of input contains a single number n (1 ≤ n ≤ 3 × 105). It is an amount of performed operations. The following n lines contain descriptions of operations. The format is described above. For all operations the value of parameter k satisfies the inequality 0 ≤ k ≤ n.

Output

For each third type operation output its result on a separate line.

ExampleInput
12
1 0 8 1
3 1
3 2
2 1
1 0 8 3
3 1
3 2
1 0 4 5
3 1
3 2
3 3
3 5
Output
9
0
1
1
1
0
1
-1

加入题单

上一题 下一题 算法标签: