Walk

Олiмпiя пiсля проведення реформ транспортної системи стала процвiтаючею країною з неймовiрно гарними мiстами та рiвними дирогами. Кожна дорога має свою красу, а за красу треба платити, цiною шляху який ми пройшли є найбiльше зi значень краси для дорiг в цьому шляху. Тобто, якщо ми пройшли по дорогам з красою [3, 1, 6, 4, 5] то за цей шлях потрiбно буде сплатити 6 монет. Кожне мiсто j має свiй тип T[j] , типи можуть повторюватись.

Тепер країнi потрiбна реформа туристичної системи, влада планує вiдкирити q туристичних маршрутiв i з яких починається в мiстi x[i] та закiнчується в мiстi y[i]. При цьому маршрут i повинен проходити не менше нiж через k[i] мiст рiзних типiв.

Варто помiтити, що якщо ми заплатили f монет, то ми зможемо скiльки завгодно раз проходити по дорогам з такою або меншою цiною, тому шлях може бути не простий та мiстити цикли.

Ви гарно зарекомендували себе в проведеннi попереднiх реформ тому влада знову просить вашої допомоги. Для заданих владою маршрутiв виведiть мiнiмальну можливу цiну. Ви можете самi ви-рiшувати якi мiста вiдвiдувати i по яким дорогам ходити, головне щоб шлях i починався в мiстi x[i] i закiнчувавсяв в y[i] та проходив не меншне нiж через k[i] рiзних за типом мiст.

Вхідні дані

В першому рядку знаходиться три числа N , M та Q - кiлькiсть мiст та кiлькiсть дорiг в країнi.

В другому рядку знаходиться N чисел, j-те число задає тип j-го мiста T[j] .

В наступних M рядках мiститься опис дорiг. Кожен рядок мiстить по 3 числа a[j] , b[j] , c[j] , дорога з’єднує мiста a[j] та b[j] i має красу c[j] .

В наступних q рядках мiститься опис маршрутiв, кожен маршрут задано 3 числами x[i], y[i], k[i] як описано в умовi.

1 ≤ T[j] ≤ 10^51 ≤ c[j] ≤ 10^51 ≤ a[j], b[j] , x[i], y[i] ≤ N2 ≤ k[i] ≤ N**1 ≤ q ≤ 10^4

Вихідні дані

Виведiть q чисел по одному в рядку. Число в i-тому рядку - це мiнiмальна можлива цiна для маршруту i. Якщо такий маршрут неможливий виведiть 1.

####Оцінювання

25 балiв 2 ≤ N,M,Q ≤ 100, k[i] = 2

35 балiв 2 ≤ N,M,Q ≤ 100

40 балiв 2 ≤ N,M ≤ 10^5

Приклади

Примітка

В першому маршрутi першого тесту потрiбно пройти по шляху 3 → 2 → 1 → 2 → 3 → 4 в такому випадку ми пройдем по дорогам з наступними значеннями краси: [3; 5; 5; 3; 2] тобто цiна шляху є 5.