Divine Chaos Simulation in Four-Dimensional Space

In a four-dimensional space, God manipulates chaos. There are n days during which the chaos of a three-dimensional world is observed. At the end of day \(i\), the chaos is \(x_i\). Due to natural causes, the chaos increases by \(d_i\) on day \(i\), but to maintain the balance of the world, there is an upper limit \(l_i\) on the chaos every day. Hence, the chaos update is given by:

$$x_i = \min\{x_{i-1}+ d_i,\ l_i\}.$$

God wishes to conduct a series of tests on this four-dimensional space. There are the following operations:

1. Test 1: Given \(a, b\) and \(k\), for every \(c\) with \(a \le c \le b\), run a simulation starting at day \(c\) with initial chaos \(l_{c-1}\) (the upper limit from the previous day) through day \(b\) according to the above formula, and record the final chaos \(x_b\). Output the \(k\)-th largest \(x_b\) among these values. It is guaranteed that \(1 \le a \le b \le n\) and \(1 \le k \le b-a+1\).
2. Test 2: Given \(a, b\) and \(x_0\), for every \(c\) with \(a \le c \le b\), run the simulation starting with initial chaos \(x_0\) (which may be larger than \(l_{c-1}\)) and output the maximum \(x_b\) among these values. \(1 \le a \le b \le n\).
3. Test 3: Given \(a\) and \(b\), for every \(c\) with \(a \le c \le b\), run the simulation starting with initial chaos \(l_{c-1}\) and output the number of distinct final chaos values \(x_b\). \(1 \le a \le b \le n\).

In addition, God may modify some values of \(l_i\). Specifically, there is an update operation:

• Update: Given \(i\) and \(newL\), update \(l_i\) to \(newL\) for \(1 \le i \le n\).

Input Format: The first line contains two integers \(n\) and \(q\) where \(n\) is the number of days and \(q\) is the total number of queries. The second line contains \(n\) integers \(d_1, d_2, \ldots, d_n\) (the chaos increments). The third line contains \(n+1\) integers \(l_0, l_1, \ldots, l_n\) (the chaos upper limits, note that \(l_0\) is used as the initial chaos for simulations starting at day 1 when using \(l_{c-1}\)). The following \(q\) lines each represent a query. Each query starts with a type indicator \(t\):

• If \(t=1\): Three integers \(a\), \(b\), and \(k\) follow.
• If \(t=2\): Three integers \(a\), \(b\), and \(x_0\) follow.
• If \(t=3\): Two integers \(a\) and \(b\) follow.
• If \(t=4\): Two integers \(i\) and \(newL\) follow.

Simulation Process: For a given starting day \(c\) (\(1 \le c \le n\)), the initial chaos is set as either \(l_{c-1}\) (for tests 1 and 3) or \(x_0\) (for test 2). Then for each day \(i\) from \(c\) to \(b\), update:

$$x_i = \min\{x_{i-1} + d_i,\ l_i\}.$$

Output the results for queries of type 1, 2, and 3. There is no output for update (type 4) queries.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) representing the number of days and the number of queries.

The second line contains \(n\) integers \(d_1, d_2, \ldots, d_n\), where \(d_i\) is the increment of chaos on day \(i\).

The third line contains \(n+1\) integers \(l_0, l_1, \ldots, l_n\). Note that \(l_0\) is used as the initial chaos for simulations starting at day 1 when using \(l_{c-1}\).

Then follow \(q\) lines, each representing a query. Each query starts with an integer \(t\). Depending on the value of \(t\), the query is one of:

• \(t = 1\): Followed by integers \(a\), \(b\), and \(k\).
• \(t = 2\): Followed by integers \(a\), \(b\), and \(x_0\).
• \(t = 3\): Followed by integers \(a\) and \(b\).
• \(t = 4\): Followed by integers \(i\) and \(newL\) to update \(l_i\) to \(newL\) (for \(1 \le i \le n\)).

outputFormat

For each query of type 1, 2, and 3, output the corresponding integer result on a separate line. There is no output for type 4 (update) queries.

sample

5 6
3 1 4 1 5
0 5 3 10 2 10
1 2 4 2
2 1 5 4
3 2 5
4 3 6
1 2 5 1
2 3 4 8

2
9
1
7
2

</p>