Мой дед — опытный лесник, он знает каждую полянку (их всего $$$N$$$ штук в лесу), каждую тропинку между определёнными двумя полянками, по которой можно ходить только в одну сторону (а тропинок $$$M$$$ штук), а также сколько на каждой тропинке растёт грибов и ягод в любой день.
Мой дед — человек привычки, и, как он рассказывал, привык он ходить в лес каждый день, начиная с полянки под номером $$$1$$$ и заканчивая на полянке под номером $$$N$$$. Естественно, что тропинки в лесу устроены так, что, проходя последовательно по ним, никогда не заблудишься, то есть не попадёшь на полянку, на которой уже был.
Мой дед ходил в лес в каждый из $$$Q$$$ дней лета, а в это время года на каждой полянке находится по рынку, где можно продавать грибы и ягоды. В $$$i$$$-й день на любой полянке можно продать грибы за $$$a_i$$$ рублей за штуку, а также ягоды за $$$b_i$$$ рублей за штуку. Мой дед же рассказывал, что каждый день, проходя каждую тропинку, он сразу же продавал все собранные на ней грибы и ягоды на соответствующем рынке по текущему курсу, причём на грибах он всегда зарабатывал больше, чем на ягодах.
Мой дед — любитель преувеличить свои достижения, поэтому мне нужна Ваша помощь. Определите для каждого из дней, правда ли, что мой дед смог пройти от $$$1$$$-й полянки до $$$N$$$-й и заработать на грибах больше, чем на ягодах, после прохождения каждой из тропинок. Заметьте, что в разные дни мой дед мог выбирать различный маршрут.
В первой строке даны три целых числа $$$N$$$, $$$M$$$ и $$$Q$$$ — количество полянок и тропинок в лесу и количество дней лета $$$(2 \le N \le 10^5, 1 \le M,Q \le 10^5)$$$.
В следующих $$$M$$$ строках описаны тропинки четырьмя целыми числами $$$u_i$$$, $$$v_i$$$, $$$s_i$$$ и $$$w_i$$$ — номера полянок из которой и в которую ведёт тропинка и количество грибов и ягод на этой тропинке в любой день $$$(1 \le u_i, v_i \le 10^5, u_i \neq v_i, 1 \le s_i, w_i \le 10^9)$$$.
В следующих $$$Q$$$ строках даны по два целых числа $$$a_j$$$ и $$$b_j$$$ — стоимость одного гриба и одной ягоды в $$$j$$$-й день $$$(1 \le a_j, b_j \le 10^9)$$$.
Гарантируется, что две различные тропинки не могут соединять одну и ту же пару полянок, а также, что они не образуют цикл.
Выведите $$$Q$$$ строк. В $$$i$$$-й строке выведите «YES», если в $$$i$$$-й день мой дед смог пройти так, как он рассказывал, либо «NO» в противном случае.
3 3 3 1 2 2 4 2 3 3 9 1 3 10 50 58 9 60 23 61 9
YES NO YES