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

В нашей системе имеются n струн с номерами от 1 до n, которые размещены в строках S = i для i = 1, ..., n на декартовой плоскости OTP, где OT представляют временные рамки, а OS представляют текущую струну частицы. Частицы движутся только в будущее и, возможно, прыгают между струнами, расходуя энергию. Первоначально только частицы могут оставаться в состоянии покоя без потери энергии, т.е. переход из состояния (t, p) в (t + 1, p ) стоит 0 энергии, и никаких других переходов в нашей системе (пока) не предусмотрено. Обратите внимание, что наша система не поддерживает путешествия назад во времени (или предполагает, что стоимость перехода назад во времени бесконечна). Ваша основная цель будет заключаться в вычислении минимального количества энергии, которое требуется частице для перемещения от струны s1 во временном интервале t1 к струне s2 во временном интервале t2, либо сказать, что это невозможно.

Теперь мы опишем определенные внешние силы, которые могут появиться: телепорты и массивные объекты. Когда телепорт появляется во временном интервале t с затратами энергии (a1, ..., an-1), он позволяет любой частице в состоянии (t, i) немедленно перейти в состояние (t, i + 1) с потерей энергии ai или в состояние (t , i - 1) с потерей энергии ai-1 (когда струна i + 1 или i - 1 существует). Если мы добавим массивный объект на временном интервале t с энергиями (b1, ..., bn), то это повлияет на переход между временем t и t + 1, так что частица в струне i требует затрат энергии bi, чтобы оставаться в той же струне (иначе частица просто исчезнет в пространстве-времени). Итак, имеется 3 типа запросов, которые Вы должны выполнить:

• 1 ta1, ..., an-1 - добавить телепорт в момент времени t с энергиями ai;
• 2 tb1, ..., bn - добавить массивный объект в момент времени t с энергиями bi;
• 3t1 s1 t2 s2 - мы столкнулись с частицей, путешествующей между состояниями (t1, s1) → (t2, s2), какое минимальное количество энергии следует затратить этой частице?

Обратите внимание, что если Вам предлагается добавить 2 телепорта / массивных объекта в один и тот же период времени, то более поздний заменяет более ранний.

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

В первой строке указаны два числа n и q - количество струн в нашей системе и количество запросов (1 ≤ n ≤ 11, 1 ≤ q ≤ 104).

В следующих q строках дается описание запросов в формате, описанном в условии, с ограничениями:

• 0 ≤ ai, bi ≤ 100 - стоимости энергий;
• 1 ≤ t ≤ 5 * 104, 1 ≤ t1 ≤ t2 ≤ 5 * 104 - временные рамки;
• 1 ≤ s1, s2 ≤ n - положение струн.

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

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