Suffix Weight XOR Query

You are given n pairs \((a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)\)

For an index \(i\) \((1 \le i \le n)\), define its weight as follows. First, form an array by concatenating \(a_1\) copies of \(b_1\), \(a_2\) copies of \(b_2\), …, \(a_i\) copies of \(b_i\). Let the mode of this array be the number that appears the most frequently. In case not all numbers appear with the same frequency and there is a tie for the maximum frequency, you may choose any one of them; however, if all numbers appear the same number of times then the mode is defined to be the largest number. The weight at index \(i\) is then defined as:

[ \text{weight}_i = (\text{mode of the first } i \text{ pairs}) \times a_i. ]

You will be given m operations. There are two types of operations:

• 1 x y: Increase \(a_x\) by \(y\) (guaranteed \(y \ge 0\)).
• 2 q: Find the smallest positive integer \(k\) such that the XOR sum of the weights for indices \(n-k+1, n-k+2, \ldots, n\) equals \(q\). It is guaranteed that a solution exists and the sum of all answers \(\sum k\) does not exceed \(5 \times 10^7\).

For each query (type 2), output the corresponding \(k\) in a separate line.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of pairs and the number of operations.

The next \(n\) lines each contain two integers \(a_i\) and \(b_i\) \((1 \le i \le n)\).

The following \(m\) lines describe an operation in one of the following two formats:

• 1 x y: Increase \(a_x\) by \(y\) (with \(y \ge 0\)).
• 2 q: Query for the smallest positive integer \(k\) such that the XOR sum of the weights for indices \(n-k+1 \ldots n\) is \(q\).

outputFormat

For each query operation (type 2), output the corresponding answer (the minimal \(k\)) on a separate line.

sample

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

2
2