Теорія струн

Одна з найпопулярніших і (на думку багатьох фізиків) багатообіцяючих теорій — це теорія струн. Вона стверджує, що мультивсесвіт складається з різних вимірів, причому найбільшим є 11-й вимір. За межами 11 вимірів Всесвіт стає нестабільним, а виміри, що перевищують 11, схлопнуться в 11-вимірний Всесвіт. Тепер перед вами стоїть завдання моделювання теоретичної проблеми струн.

У нашій системі є n струн, пронумерованих від 1 до n, які розташовані в рядках S = i для i = 1, ..., n на декартовій площині OTP, де OT представляє часові рамки, а OS представляє поточну струну частинки. Частинки рухаються тільки вперед у часі і можуть стрибати між струнами, витрачаючи енергію. Спочатку частинки можуть залишатися в стані спокою без втрати енергії, тобто перехід зі стану (t, p) в (t + 1, p) коштує 0 енергії, і жодних інших переходів у нашій системі (поки) не передбачено. Зверніть увагу, що наша система не підтримує подорожі назад у часі (або припускає, що вартість переходу назад у часі нескінченна). Ваше основне завдання — обчислити мінімальну кількість енергії, необхідну частинці для переміщення від струни s[1] у часовому інтервалі t[1] до струни s[2] у часовому інтервалі t[2], або визначити, що це неможливо.

Тепер ми опишемо певні зовнішні сили, які можуть з'явитися: телепорти і масивні об'єкти. Коли телепорт з'являється у часовому інтервалі t з витратами енергії (a[1], ..., a[n-1]), він дозволяє будь-якій частинці в стані (t, i) негайно перейти в стан (t, i + 1) з втратою енергії a[i] або в стан (t, i - 1) з втратою енергії a[i-1] (якщо струна i + 1 або i - 1 існує). Якщо ми додамо масивний об'єкт у часовому інтервалі t з енергіями (b[1], ..., b[n]), це вплине на перехід між часом t і t + 1, так що частинка в струні i вимагає витрат енергії b[i], щоб залишатися в тій самій струні (інакше частинка просто зникне в просторі-часі). Отже, є 3 типи запитів, які ви повинні виконати:

• 1 t a[1], ..., a[n-1] - додати телепорт у момент часу t з енергіями a[i];

• 2 t b[1], ..., b[n] - додати масивний об'єкт у момент часу t з енергіями b[i];

• 3 t[1] s[1] t[2] s[2] - ми маємо частинку, що подорожує між станами (t[1], s[1]) → (t[2], s[2]), яку мінімальну кількість енергії слід витратити цій частинці?

Зверніть увагу, що якщо вам пропонується додати 2 телепорти або масивні об'єкти в один і той самий період часу, то пізніший замінює раніший.

Вхідні дані

У першому рядку вказані два числа n і q — кількість струн у нашій системі і кількість запитів (1 ≤ n ≤ 11, 1 ≤ q ≤ 10^4).

У наступних q рядках дається опис запитів у форматі, описаному в умові, з обмеженнями:

• 0 ≤ a[i], b[i] ≤ 100 — вартості енергій;

• 1 ≤ t ≤ 5 * 10^4, 1 ≤ t[1] ≤ t[2] ≤ 5 * 10^4 — часові рамки;

• 1 ≤ s[1], s[2] ≤ n — положення струн.

Вихідні дані

Для кожного запиту третього типу виведіть єдине число — відповідь на нього.

Приклади