У Потоколяндії є будинків, у -му з яких проживають a_i мешканців. Між цими будинками є доріг, кожна дорога сполучає будинки v_i і u_i. Ми визначаємо щастя кожного мешканця як кількість мешканців (включно з собою), яких він може зустріти. Житель будинку може зустріти іншого жителя, якщо він з його будинку, або з будинку до якого можна дістатися, подорожуючи по дорогах Потоколяндії.
Останні днів кожного дня відбувалася подія одного з двох типів:
Снігом засипало дорогу між будинками g_i і h_i, тож тепер по ній не можна проїхати.
k_i мешканців w_i-го будинку на вертольоті відправлялися у гості до далеких родичів за межами Потоколяндії.
Мешканці Потоколяндії пишуть листи Козаку Вусу з проханням повідомити їм останній такий день, що сума щастя будь-якого мешканця x_i-го будинку та будь-якого мешканця y_i-го будинку принаймні z_i.
Можна вважати, що всі дії відбуваються миттєво в першу мить кожного дня. Якщо і до початку всіх подій сумарне щастя менше за z_i, то потрібно вивести . Якщо сумарне щастя було не менше за z_i лише до першої події, то потрібно вивести . Якщо після -ої події сумарне щастя стало меншим, ніж потрібно, то потрібно вивести i - 1. Якщо після всіх подій сумарне щастя принаймні z_i, то потрібно вивести .
Оскільки Козак Вус досить зайнята людина, а мешканців Потоколяндії багато, він просить Вас допомогти йому відповісти на всі листи.
Перший рядок містить чотири цілих числа , , та (1 \le n, m, d, s \le 2 \cdot 10^5) — кількість будинків, доріг, днів та повідомлень відповідно.
Наступний рядок містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — кількість жителів в -му будинку.
Кожний з наступних рядків містить по два цілих числа v_i та u_i (1 \leq v_i, u_i \leq n, u_i \neq v_i) — будинки між якими є дорога. Гарантується, що немає кратних ребер.
Кожен з наступних рядків описує запит в одному з двох форматів:
«1~g_i~h_i» (1 \leq g_i, h_i \leq n) — дорога, яку засипало снігом. Гарантується, що така дорога існує, і вона не була засипана снігом раніше.
«2~w_i~k_i» (1 \leq w_i \leq n, 1 \leq k_i \leq 10^9) — номер будинку та кількість людей, які покинули його. Гарантується, що в будь-який момент часу в кожному будинку буде принаймні один мешканець.
Кожен з наступних рядків містить по три цілих числа x_i, y_i та z_i (1 \leq x_i, y_i \leq n, 1 \leq z_i \leq 10^9).
Виведіть окремих рядків, у кожному з яких відповідь на відповідний запит. Якщо сума щастя двох мешканців ще до першого дня менша , то виведіть .
Example 1
Example 2
Пояснення другого прикладу:
Для першого запиту сумарне щастя двох мешканців завжди буде менше (спочатку воно рівне ). Для другого запиту, після другого дня їх сумарне щастя буде зменшено до 6 + 4 = 10. Інші запити пояснюються так само.
