Теория струн
Теория струн
Одна из самых популярных и (по мнению многих физиков) многообещающих - теория струн. В нем говорится, что мультивселенная состоит из разных измерений, но наибольшим является 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 t
a1
, ...,an-1
- добавить телепорт в момент времени t с энергиямиai
; - 2 t
b1
, ...,bn
- добавить массивный объект в момент времени t с энергиямиbi
; - 3
t1 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 - положение струн.
Выходные данные
Для каждого запроса третьего типа выведите единственное число - ответ на него.
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
10 -1 2 10 12 6 3 5 4