Simulate Dr. P's Integer Operations

Dr. P abstracts his computational task as operations on a single integer \(x\), which is initially \(0\). You will be given \(n\) operations. There are two types of operations:

• 1 a b: Add \(a\cdot 2^b\) to \(x\), where \(a\) is an integer and \(b\) is a non-negative integer.
• 2 k: Query the value of the bit corresponding to \(2^k\) in the binary representation of \(x\). In other words, output the value of the \(k\)-th bit of \(x\) (with the least-significant bit corresponding to \(k=0\)).

It is guaranteed that \(x\geqslant 0\) at all times.

Input Format: The first line contains an integer \(n\) indicating the number of operations. Each of the next \(n\) lines contains an operation in one of the formats described above.

Output Format: For every query operation (type 2), output the result on a new line.

inputFormat

The first line contains a single integer \(n\) denoting the number of operations. The following \(n\) lines each contain an operation in one of the following two formats:

• 1 a b: Add \(a\cdot 2^b\) to \(x\).
• 2 k: Query the value of the \(k\)-th bit of \(x\) (i.e. the bit corresponding to \(2^k\)).

outputFormat

For each query operation (type 2), output a single line containing the value of the queried bit (either 0 or 1).

sample

5
1 3 0
2 0
1 1 1
2 1
2 0

1
0
1