У току је планирање прве фазе београдског метроа, која ради једноставности вози искључиво са југа на север (ко жели да се вози назад иде трамвајем). Постоји \(N\) станица метроа, и оне се могу поделити у три групе: јужне (јужно од Саве), северне (северно од Саве), и средишње (које се налазе баш испод корита Саве). Једна од јужних станица је главна полазна станица и има редни број 1, а једна од северних станица је главна долазна станица и има редни број 2.

\(M\) једносмерних метро тунели повезује станице. Важи следеће:

• Тунели које крећу из јужних станица иду до јужних или средишњих станица.
• Тунели које крећу из средишњих или северних станица иду до северних станица.
• Јужне станице имају тачно један улазни тунел, осим главне полазне станице, у коју не улази ниједан тунел.
• Северне станице имају тачно један излазни тунел, осим главне долазне станице, из које не излази ниједан тунел.
• Средишње станице имају тачно један улазни и један излазни тунел.
• Мапа метроа се може нацртати тако да се тунели не секу, при чему је редослед станица на улазу исти као редослед на мапи са истока на запад (свака станица је источно од оних са већим индексом) и важи да уколико постоји тунел од станице \(u\) до станице \(v\), онда је на мапи станица \(u\) јужније од станице \(v\).
• Гарантује да се у сваку станицу може стићи из главне полазне станице, и да се из сваке станице може стићи у главну долазну станицу.

Дата вам је мапа метроа и време потребно да се прође кроз сваки од тунела. Потребно је да одговорите на \(Q\) упита следећих типова:

• Промени време потребно да се прође кроз дати тунел на \(t\).
• Одреди време потребно да се стигне од главне полазне до главне долазне станице \(K\)-тим најбржим путем (гарантује се да ће постојати бар \(K\) путева).

Описи функција

Потребно је да имплементирате функцију

• \(\text{Resi}(N, M, U[\dots], V[\dots], C[\dots], Q, A[\dots], B[\dots], R[\dots])\)

где је:

• \(N\) број станица.
• \(M\) број тунела.
• \(U\), \(V\), \(C\) низови дужине \(M\) који описују тунеле: \(i\)-ти тунел иде од станице \(U[i]\) до \(V[i]\) и потребно је \(C[i]\) секунди да се прође.
• \(Q\) број упита.
• \(A\) и \(B\) низови дужине \(Q\) који садрже упите, а \(R\) низ дужине \(Q\) у који је потребно записати резултате упита. Конкретно, за \(i\)-ти упит:
  • Ако \(A[i] = -1\), потребно је у \(R[i]\) записати време потребно да се стигне од главне полазне до главне долазне станице \(B[i]\)-тим најбржим путем.
  • У супротном, потребно је променити време проласка кроз \(A[i]\)-ти тунел на \(B[i]\) и оставити вредност \(R[i]\) непромењену.

Сви низови су индексирани од 1.

Пример

Нека је \(N = 6\), \(M = 7\), \(U = [1, 1, 5, 5, 3, 4, 6]\), \(V = [5, 6, 3, 4, 2, 2, 2]\), \(C = [1, 8, 2, 4, 5, 5, 2]\), \(Q = 4\), \(A = [-1, -1, 6, -1]\) и \(B = [1, 3, 7, 3]\).

Овај улаз описује метро у ком су станице \(1\) (главна полазна) и \(5\) јужне, станице \(3\), \(4\) и \(6\) средишње и станица \(2\) (главна долазна) северна. Могући путеви су:

• \(1 \to 5 \to 3 \to 2\), са временом \(8\),
• \(1 \to 5 \to 4 \to 2\), са временом \(10\), и
• \(1 \to 6 \to 2\), са временом \(10\).

Одговор на први упит је време кроз најбржи пут (\(8\)), а на други време кроз трећи најбржи пут (\(10\)). Након трећег упита време кроз последњи пут постаје \(12\) (јер је дужина тунела \(4 \to 2\) повећана), што је и одговор на последњи упит.

Дакле, очекиван излаз је \(R = [8, 10, ?, 12]\), где \(?\) представља члан који одговара упиту у ком се мења време проласка кроз тунел.

Ограничења

• \(3 \leq N \leq 50000\).
• \(1 \leq Q \leq 20000\).
• \(N-1 \leq M \leq 2N-4\).
• Дужине тунела (и оригиналне, и након промене) су у интервалу \([0, 10^4]\).

Подзадаци

Тест примери су подељени у шест подзадатака:

• [3 поена]: \(Q = 1\).
• [6 поена]: \(N, Q \leq 1000\).
• [14 поена]: Постоји највише \(1000\) средишњих станица.
• [21 поена]: Све промене времена се односе на тунеле који крећу из средишње станице или стижу у средишњу станицу.
• [23 поена]: У свим упитима у којима се тражи време, важи \(B[i] = 1\).
• [33 поена]: Без додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл metro.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Resi(int N, int M, int *U, int *V, int *C, int Q, int *A, int *B, long long *R);

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N, M\).
• У наредних \(M\) редова по три броја. У \(i\)-том реду налазе се бројеви \(U_i, V_i, C_i\).
• У наредном реду број \(Q\).
• У наредних \(Q\) редова по два броја: \(A_i\) и \(B_i\).

Затим овај програм зове вашу функцију и штампа одговоре на упите које функција попуни у низу \(R\).