Мой дед — опытный лесник, он знает каждую полянку (их всего N штук в лесу), каждую тропинку между определёнными двумя полянками, по которой можно ходить только в одну сторону (а тропинок M штук), а также сколько на каждой тропинке растёт грибов и ягод в любой день.

Мой дед — человек привычки, и, как он рассказывал, привык он ходить в лес каждый день, начиная с полянки под номером 1 и заканчивая на полянке под номером N. Естественно, что тропинки в лесу устроены так, что, проходя последовательно по ним, никогда не заблудишься, то есть не попадёшь на полянку, на которой уже был.

Мой дед ходил в лес в каждый из Q дней лета, а в это время года на каждой полянке находится по рынку, где можно продавать грибы и ягоды. В i-й день на любой полянке можно продать грибы за a_i рублей за штуку, а также ягоды за b_i рублей за штуку. Мой дед же рассказывал, что каждый день, проходя каждую тропинку, он сразу же продавал все собранные на ней грибы и ягоды на соответствующем рынке по текущему курсу, причём на грибах он всегда зарабатывал больше, чем на ягодах.

Мой дед — любитель преувеличить свои достижения, поэтому мне нужна Ваша помощь. Определите для каждого из дней, правда ли, что мой дед смог пройти от 1-й полянки до N-й и заработать на грибах больше, чем на ягодах, после прохождения каждой из тропинок. Заметьте, что в разные дни мой дед мог выбирать различный маршрут.

В первой строке даны три целых числа N, M и Q — количество полянок и тропинок в лесу и количество дней лета (2 ≤ N ≤ 10⁵, 1 ≤ M, Q ≤ 10⁵).

В следующих M строках описаны тропинки четырьмя целыми числами u_i, v_i, s_i и w_i — номера полянок, из которой и в которую ведёт тропинка, и количество грибов и ягод на этой тропинке в любой день (1 ≤ u_i, v_i ≤ 10⁵, u_i ≠q v_i, 1 ≤ s_i, w_i ≤ 10⁹).

В следующих Q строках даны по два целых числа a_j и b_j — стоимость одного гриба и одной ягоды в j-й день (1 ≤ a_j, b_j ≤ 10⁹).

Гарантируется, что две различные тропинки не могут соединять одну и ту же пару полянок, а также что они не образуют цикл.

Выведите Q строк. В i-й строке выведите «YES», если в i-й день мой дед смог пройти так, как он рассказывал, либо «NO» в противном случае.