2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

String theory

One of the most popular and (in a lot of physicist opinion) promising is a string theory. It states, that the multiverse is made of different dimensions but the highest is 11-th dimension. Beyond 11 dimensions, the universe would become unstable and dimensions higher than 11 would collapse to an 11-dimensional universe. You are now faced the challenge in modelling String theoretical problem.

Our system has n strings numbered from 1 to n placed at the lines S = i for i = 1, ..., n on OTP Cartesian plane, where OT represent time frames and OS represent current string of the particle. Particles moving only into the future and maybe jump between the strings expending the energy. Initially, particles only can stay in a rest without losing any energy, i.e. transition from state (t, p) to (t + 1, p) costs 0 energy, and no other transitions are given within our system (yet). Note, our system does not possess backward time travelling (or assume that cost of transition back in time is infinity). Your main aim will be to calculate the minimum amount of energy particle require to travel from string s1 at the time frame t1 to the string s2 at the time frame t2, or say that this impossible to happen.

We now describe the certain external forces that may appear: teleports and massive objects. When teleport appear at time frame t with energies costs (a1, ..., an-1), it allows any particle at the state (t, i) to immediately jump to the state (t, i + 1) with energy loss ai or to the state (t, i - 1) with energy loss ai-1 (whenever the string i + 1 or i - 1 exist). If we add massive object at time frame t with energies (b1, ..., bn) it affect transition between time frames t and t + 1 so that particle at string i require to expend bi energy to stay at the same string (otherwise particle just disappear it a space-time). So there are 3 type of requests you must fulfil:

  • 1 ta1, ..., an-1 - add teleport at time frame t with energies ai;
  • 2 tb1, ..., bn - add massive object at time frame t with energies bi;
  • 3t1 s1 t2 s2 - we encountered particle travelled between the states (t1, s1) → (t2, s2), what is minimal possible amount of energy expended by this particle?

Note, that if you are told to add 2 teleports / massive objects in the same time frame, then later one replaces earlier one.


In the first line you are given two numbers n and q - number of strings in our system and number of requests (1n11, 1q104).

In the next q lines on the i-th line you are given the description of the queries in the format described in the statement with restrictions:

  • 0ai, bi100 - energy costs;
  • 1t5 * 104, 1t1t25 * 104 - time frames;
  • 1s1, s2n - string positions.


For each query of the third type output single number - the answer for the query.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 12
2 1 1 10 3
3 1 2 2 2
3 1 2 2 3
1 1 2 1
3 1 1 1 2
3 1 2 3 2
3 1 1 2 2
3 1 1 2 3
1 2 2 2
3 1 1 1 3
3 1 1 2 3
3 1 3 2 1
Output example #1
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem B