eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Теория струн

Теория струн

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Одна из самых популярных и (по мнению многих физиков) многообещающих - теория струн. В нем говорится, что мультивселенная состоит из разных измерений, но наибольшим является 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 ta[1], ..., a[n-1] - добавить телепорт в момент времени t с энергиями a[i];

  • 2 tb[1], ..., b[n] - добавить массивный объект в момент времени t с энергиями b[i];

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

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

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

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

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

  • 0a[i], b[i]100 - стоимости энергий;

  • 1t5 * 10^4, 1t[1]t[2]5 * 10^4 - временные рамки;

  • 1s[1], s[2]n - положение струн.

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

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

Пример

Входные данные #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
Выходные данные #1
10
-1
2
10
12
6
3
5
4
Источник 2021 KBTU Open, Весна Казахстан, Алма-Ата, 30 мая, Задача B