Карьеры и караваны
(Время: 0,25 сек. Память: 32 Мб Сложность: 82%)
В стране расположено N поселений-карьеров, между которыми проложено M караванных трактов. Каждый карьер разрабатывает ровно один из двух минералов: гранит – «0»; мрамор – «1».
Каждый тракт имеет целочисленную пропускную способность W: сколько единиц груза он может перевозить за день (веса могут быть как положительные, так и отрицательные – дороги бывают и убыточными). Так как горная порода многослойна, то карьер иногда вынужден переключается на добычу другого минерала (гранит → мрамор или мрамор → гранит). Правительство иногда делает запросы на суммарную пропускную способность всех трактов, которые соединяют карьеры, добывающих минералы с кодами А и В (0 0, 0 1 = 1 0, 1 1). У Вас есть журнал всех операций, необходимо вывести ответ на каждый запрос правительства.
Входные данные
Входной файл INPUT.TXT содержит в первой строке два натуральных числа N, M (1 ≤ N, M ≤ 105). Во второй строке содержится N чисел равных 0 или 1.
Далее в M строках описаны тракты u, v, w (1 ≤ u, v ≤ N; u ≠ v), обозначающих что тракт между карьерами u и v имеет пропускную способность w (1 ≤ w ≤ 106).
В следующей строке содержится натуральное число Q (1 ≤ Q ≤ 105) количество записей в журнале.
Далее в Q строках описаны операции двух видов:
- S x (символ S означает, что карьер х переключился на добычу другого минерала);
- Q A B (символ Q означает запрос правительства).
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса правительства выведите ответ с новой строки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 5
0 1 0 1
1 2 8
4 3 7
2 3 12
4 1 20
2 4 5
8
Q 1 1
Q 0 0
S 1
Q 1 1
Q 0 1
Q 1 0
S 4
Q 0 0 | 5
0
33
19
19
7 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
