Теория струн

Одна из самых популярных и (по мнению многих физиков) многообещающих - теория струн. В нем говорится, что мультивселенная состоит из разных измерений, но наибольшим является 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 - положение струн.

Выходные данные

Для каждого запроса третьего типа выведите единственное число - ответ на него.

Примеры