| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Мой дед --- опытный лесник, он знает каждую полянку (их всего $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