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

Тепер країнi потрiбна реформа туристичної системи, влада планує вiдкирити q туристичних маршрутiв i з яких починається в мiстi xi та закiнчується в мiстi yi. При цьому маршрут i повинен проходити не менше нiж через ki м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 xi i закiнчувавсяв в yi та проходив не меншне нiж через ki рiзних за типом мiст.

Вхідні дані

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

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

В наступних M рядках мiститься опис дорiг. Кожен рядок мiстить по 3 числа aj , bj , cj , дорога з’єднує мiста aj та bj i має красу cj .

В наступних q рядках мiститься опис маршрутiв, кожен маршрут задано 3 числами xi, yi, ki як описано в умовi.

1 ≤ Tj ≤ 1051 ≤ cj ≤ 1051 ≤ aj, bj , xi, yi ≤ N2 ≤ ki ≤ N** 1 ≤ q ≤ 104

Вихідні дані

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

Оцінювання

25 балiв 2 ≤ N,M,Q ≤ 100, ki = 2

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

40 балiв 2 ≤ N,M ≤ 105

Пояснення

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