Є комплекс у складі \(N\) \(10^9\)-поверхових хмарочосів. Хмарочоси пронумеровані від 1 до \(N\), а поверхи від 1 до \(10^9\). З будь-якого поверху будь-якого хмарочоса можна за допомогою небесного мосту потрапити на той самий поверх будь-якого іншого хмарочоса за одну хвилину.

Додатково є \(M\) ліфтів. \(i\)-й ліфт проходить між поверхом \(B_i\) і поверхом \(C_i\) хмарочоса \(A_i\). За допомогою цього ліфта можна піднятися з поверху \(x\) на поверх \(y\) хмарочоса \(A_i\) за |\(x-y\)| хвилин для кожної пари цілих чисел \(x,y\) такої, що \(B_i \le x,y \le C_i\).

Дайте відповідь на наступні \(Q\) запитів.

• Визначте, чи можна дістатися з поверху \(Y_i\) хмарочоса \(X_i\) до поверху \(W_i\) хмарочоса \(Z_i\), і знайдіть найкоротший час, необхідний, щоб дістатися туди, якщо це можливо.

Обмеження

• \(1 \le N,M,Q \le 2 \times 10^5\)
• \(1 \le A_i \le N\)
• \(1 \le B_i < C_i \le 10^9\)
• \(1 \le X_i,Z_i \le N\)
• \(1 \le Y_i,W_i \le 10^9\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N, M, Q\)

Наступні  \(M\) рядків містять цілі числа \(A_i, B_i, C_i\)

Далі ідуть  \(Q\) рядків із запитами \(X_i, Y_i, Z_i, W_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(Q\) рядків. \(І\)-й рядок має містити -1, якщо для \(\mathrm{query}_iquery i​\), пункт призначення недоступний; інакше він має містити мінімальну кількість хвилин, необхідних для того, щоб потрапити туди.

Примітка

До прикладу 1:

За 1-м запитом ви можете дістатися до пункту призначення за 12 хвилин наступним чином.

• Скористайтеся ліфтом 1, щоб дістатися з 3 поверху на 9 поверх хмарочоса 1 за 6 хвилин.
• Використовуйте міст на 9 поверсі, щоб дістатися від хмарочоса 1 до хмарочоса 3 за 1 хвилин.
• Скористайтеся ліфтом 3, щоб дістатися з 9 поверху на 14 поверх хмарочоса 3 за 5 хвилин.

Для 3-го запиту адресат недоступний, тому має бути надруковано -1.

Приклад вхідних даних

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

Приклад вихідних даних

12
7
-1

Приклад вхідних даних

1 1 1
1 1 2
1 1 1 2

Приклад вихідних даних

1