TL=0.1s
ML=64MB
Митко има рожден ден! Ще го празнува в своята къща в град Хасково, която се намира в кръстовище 1.
Представете си Хасково като граф без примки (може да не е изцяло свързан). Приятелите му, M на брой, се намират в кръстовище a[i], i=[1;M].
Всеки приятел иска да купи подарък на Митко, като i-тия приятел ще отиде в магазин, обозначен с кръстовище b[i] (имайте предвид, че тези кръстовища може да съвпадат с някои от къщите!).
Хасково е свързан с B на брой улици, по които могат да се движат приятелите.
Сега обаче се случи нещо извънредно - проливен дъжд наводни Хасково и някои от улиците стават непроходими.
Напишете програма birthday, която, по дадена карта на Хасково, преди всички заявки и след всяка заявка от тип „Улицата между кръстовищата u и v се затваря!“, или „Улицата между кръстовищата u и v се отваря!“ открива на кой приятел ще му отнеме най-дълго време, за да стигне до Митко, използвайки проходимите улици, и самото време. Имайте предвид, че НЕ може да се отвори улица, която не е била дадена в началото, и няма повече от 1 улица, свързваща 2 върха.

ВХОД
На първия ред на стандартния вход се въвеждат числата N, M, R, B и Q.
На следващите B реда се въвеждат две числа u, v и t - има двупосочна улица между кръстовищата u и v, която се изминава за време t.
На следващите M реда се въвеждат две числа a[i] и b[i] - позицията на i-тия приятел и магазина, който приятелят е избрал.
На следващите Q реда се въвеждат три числа type u v:
Ако type=1, тогава улицата между u и v се отваря;
Ако type=0, тогава улицата между u и v се затваря.
Всеки приятел първо отива до магазина, а след това до къщата на Митко.

ИЗХОД
На първия ред на стандартния вход се извеждат 2 числа - първото е номерът приятелят, на когото му е отнело най-дълго време, за да достигне до Митко, а второто - самото време. Ако има няколко такива отговора, изведете този, при който номера е най-малък. Ако даден приятел не може да стигне до Митко, или до съответния магазин, тогава не го бройте към отговора. Ако никой от приятелите на Митко не се брои към отговора, изведете две нули.
За всяка заявка на един ред да се изведе същото като горепосоченото, но след изпълнение на i-тата заявка.

ОГРАНИЧЕНИЯ
1<=N,M,B<=1e5;
1<=Q<=1e5;
За тестове, носещи 30 точки, 1<=N,M,B,Q<=1e3;
За тестове, носещи 80 точки, 1<=Q<=1e4;
За тестове, носещи 40 точки, t=1;
За тестове, носещи 20 точки, заявките са само от type=0;
1<=u,v<=N, u!=v;
0<=t<=1e9;
1<=a[i],b[i]<=N.

ПРИМЕРЕН ТЕСТ
Вход:
6 3 5 3
1 2 1
2 3 2
1 3 3
2 4 6
5 6 2
2 4
1 3
5 4
0 1 3
0 2 4
1 2 4

Изход:
2 13
2 13
1 6
2 13

Обяснение: Тук последният приятел не може да стигне до Митко, на първият му трябва време 6, а на вторият - 13. След втората заявка вторият приятел не може да стигне до магазина си и затова не се включва към бройката. След третата заявка приятел 2 може да стигне до Митко с подаръка си.


Преди всички заявки графа е следния:

  1  2  3
1--2--3--1
   | 6
   4
 2
5--6

След първата заявка е следния:

  1  2
1--2--3
   | 6
   4
 2
5--6

След втората:

  1  2
1--2--3

   4
 2
5--6

След третата:

  1  2
1--2--3
   | 6
   4
 2
5--6
