Sequential Transformation Operations

You are given (n) transformations. The (i)-th transformation has two attributes (p_i) and (q_i), and when this transformation is applied to an integer (x) it produces [ f_i(x)=\left\lfloor\frac{x}{p_i}\right\rfloor+q_i ]

There are (m) operations of two types:

• Modification: Update the attributes of a transformation.
• Query: Given an integer \(x\) and two indices \(s\) and \(t\) (1-indexed), compute and output the value of \[ f_{t}(f_{t-1}(\cdots f_{s+1}(f_{s}(x))\cdots )) \]

The transformation function definition is provided in LaTeX above. Modify operations update the parameters (p_i) and (q_i) of the corresponding transformation, and query operations require you to sequentially apply the transformations in the given range.

inputFormat

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

The next \(n\) lines each contain two integers \(p_i\) and \(q_i\) describing the attributes of the transformations.

Each of the following \(m\) lines describes an operation. An operation is in one of the following two formats:

• 1 i p q — A modify operation which sets the \(i\)-th transformation's parameters to \(p\) and \(q\) (1-indexed).
• 2 x s t — A query operation that requires you to compute \(f_t(f_{t-1}(\cdots f_s(x)\cdots))\).

outputFormat

For each query operation, output the resulting integer on a separate line.

sample

3 4
2 1
3 2
1 3
2 10 1 2
1 2 2 1
2 10 1 3
2 5 2 3

4
7
6