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 s[1] at the time frame t[1] to the string s[2] at the time frame t[2], 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 (a[1], ..., a[n-1]), it allows any particle at the state (t, i) to immediately jump to the state (t, i + 1) with energy loss a[i] or to the state (t, i - 1) with energy loss a[i-1] (whenever the string i + 1 or i - 1 exist). If we add massive object at time frame t with energies (b[1], ..., b[n]) it affect transition between time frames t and t + 1 so that particle at string i require to expend b[i] 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 t a[1], ..., a[n-1] - add teleport at time frame t with energies a[i];

• 2 t b[1], ..., b[n] - add massive object at time frame t with energies b[i];

• 3 t[1] s[1] t[2] s[2] - we encountered particle travelled between the states (t[1], s[1]) → (t[2], s[2]), 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.

Input

In the first line you are given two numbers n and q - number of strings in our system and number of requests (1 ≤ n ≤ 11, 1 ≤ q ≤ 10^4).

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:

• 0 ≤ a[i], b[i] ≤ 100 - energy costs;

• 1 ≤ t ≤ 5 * 10^4, 1 ≤ t[1] ≤ t[2] ≤ 5 * 10^4 - time frames;

• 1 ≤ s[1], s[2] ≤ n - string positions.

Output

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

Examples