Козак Вус і Потоколяндія

У Потоколяндії є $n$ будинків, у $i$-му з яких проживають $a_i$ мешканців. Між цими будинками є $m$ доріг, кожна дорога сполучає будинки $v_i$ і $u_i$. Ми визначаємо щастя кожного мешканця як кількість мешканців (включно з собою), яких він може зустріти. Житель будинку може зустріти іншого жителя, якщо він з його будинку, або з будинку до якого можна дістатися, подорожуючи по дорогах Потоколяндії.

Останні $d$ днів кожного дня відбувалася подія одного з двох типів:

1. Снігом засипало дорогу між будинками $g_i$ і $h_i$, тож тепер по ній не можна проїхати.

2. $k_i$ мешканців $w_i$-го будинку на вертольоті відправлялися у гості до далеких родичів за межами Потоколяндії.

Мешканці Потоколяндії пишуть листи Козаку Вусу з проханням повідомити їм останній такий день, що сума щастя будь-якого мешканця $x_i$-го будинку та будь-якого мешканця $y_i$-го будинку принаймні $z_i$.

Можна вважати, що всі дії відбуваються миттєво в першу мить кожного дня. Якщо і до початку всіх подій сумарне щастя менше за $z_i$, то потрібно вивести $-1$. Якщо сумарне щастя було не менше за $z_i$ лише до першої події, то потрібно вивести $0$. Якщо після $i$-ої події сумарне щастя стало меншим, ніж потрібно, то потрібно вивести $i-1$. Якщо після всіх подій сумарне щастя принаймні $z_i$, то потрібно вивести $d$.

Оскільки Козак Вус досить зайнята людина, а мешканців Потоколяндії багато, він просить Вас допомогти йому відповісти на всі листи.

Вхідні дані

Перший рядок містить чотири цілих числа $n$, $m$, $d$ та $s$ ($1\le n,m,d,s\le 2\cdot 10^5$) — кількість будинків, доріг, днів та повідомлень відповідно.

Наступний рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — кількість жителів в $i$-му будинку.

Кожний з наступних $m$ рядків містить по два цілих числа $v_i$ та $u_i$ ($1\le v_i,u_i\le n$, $u_i\ne v_i$) — будинки між якими є дорога. Гарантується, що немає кратних ребер.

Кожен з наступних $d$ рядків описує запит в одному з двох форматів:

• «$1g_i{h}_i$» ($1\le g_i,h_i\le n$) — дорога, яку засипало снігом. Гарантується, що така дорога існує, і вона не була засипана снігом раніше.

• «$2w_i{k}_i$» ($1\le w_i\le n$, $1\le k_i\le 10^9$) — номер будинку та кількість людей, які покинули його. Гарантується, що в будь-який момент часу в кожному будинку буде принаймні один мешканець.

Кожен з наступних $s$ рядків містить по три цілих числа $x_i$, $y_i$ та $z_i$ ($1\le x_i,y_i\le n$, $1\le z_i\le 10^9$).

Вихідні дані

Виведіть $s$ окремих рядків, у кожному з яких відповідь на відповідний запит. Якщо сума щастя двох мешканців ще до першого дня менша $z$, то виведіть $-1$.

Приклади

Примітка

Пояснення другого прикладу:

Для першого запиту сумарне щастя двох мешканців завжди буде менше $21$ (спочатку воно рівне $20$). Для другого запиту, після другого дня їх сумарне щастя буде зменшено до $6+4=10$. Інші запити пояснюються так само.

Оцінювання