Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

F. A+B
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard 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.

Example
Input
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