E. Путешествие по царству Снежной королевы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Герда пустилась в путь по царству Снежной королевы.

Дорожная сеть, по которой направляется Герда, представляет собой n перекрёстков, соединённых m дорогами. Дороги пронумерованы числами от 1 до m. Снежная королева догадывалась, что Кая могут найти, и наложила на них могучее заклятие. Теперь погодные условия на дороге с номером i таковы, что в какой бы момент времени, не превосходящий i, Герда ни оказалась на ней, она выедет с неё только в момент времени i. Если же она ступит на дорогу позже, чем в момент времени i, она так и не сможет с неё выехать.

Герда выезжает в момент времени l с перекрёстка с номером s и едет во дворец Снежной королевы, расположенный на перекрёстке с номером t. Кроме того, в момент времени r + 1 Снежная королева возвращается в свой дворец и уже не пустит Герду внутрь, поэтому Герда должна добраться до дворца не позже, чем в момент времени r.

Вам требуется по заданной сети для каждого из q запросов li, ri, si и ti ответить, сможет ли Герда добраться до дворца Снежной королевы.

Входные данные

В первой строке входных данных находятся числа n, m и q (2 ≤ n ≤ 1000, 1 ≤ m, q ≤ 200 000) — количество перекрёстков в дорожной сети царства Снежной королевы, дорог в ней, случаев расположения Герды, дворца Снежной королевы и времён выезда Герды и возвращения Снежной королевы соответственно.

В i-й из следующих m строк дано описание дороги с номером i. Описание состоит из целых чисел vi и ui (1 ≤ vi, ui ≤ n, vi ≠ ui) — номеров перекрёстков, соединённых этой дорогой. По дороге можно добраться как из перекрёстка vi на перекрёсток ui, так и из перекрёстка ui в перекрёсток vi. Каждая пара перекрёстков может встречаться более одного раза, это значит, что между ними есть несколько разных дорог.

Затем следуют описания тестовых случаев. В каждой из следующих q строк содержатся четыре числа li, ri, si и ti (1 ≤ li ≤ ri ≤ m, 1 ≤ si, ti ≤ n, si ≠ ti) — момент времени, когда Герда выезжает, самый поздний момент времени, когда она может приехать во дворец, номер перекрёстка, с которого выезжает Герда, и номер перекрёстка, на котором расположен дворец Снежной Королевы.

Выходные данные

Для каждого тестового случая выведите «Yes» (без кавычек) или «No» (без кавычек) — сможет Герда добраться до дворца Снежной королевы или нет.

Пример
Входные данные
5 4 6
1 2
2 3
3 4
3 5
1 3 1 4
1 3 2 4
1 4 4 5
1 4 4 1
2 3 1 4
2 2 2 3
Выходные данные
Yes
Yes
Yes
No
No
Yes