29193번 - Башни 스페셜 저지다국어

Петя и Вася очень любят играть в одну настольную игру. Правила этой игры довольно сложные и мы не будем их описывать в условии в полной мере. На карте для этой игры в два ряда расположены башни. Некоторые башни верхнего ряда соединены дорогами с башнями нижнего ряда. В начале каждый игрок владеет ровно одной башней. Причем первый игрок владеет башней из верхнего ряда, а второй из нижнего. Цель каждого игрока --- захватить все башни.

У каждой башни есть своя цена. Каждую игру стоимость башен выбирается случайным образом для того, чтобы не получалось так, что всегда выигрывает, например, первый игрок. Вася и Петя заметили, что игра получается совсем не интересной, если в самом начале игры башни, которые им принадлежат, соединены дорогой. В этом случае один из игроков сможет захватить башню соперника, и игра закончится на первом же ходу. Также они заметили, что чем больше суммарная стоимость башен, которыми они владеют на первом ходу, тем игра получается интересней.

Васе и Пете надоело самим выбирать начальное положение для игры, и они попросили у вас помощи. Пронумеруем башни верхнего ряда слево направо начиная с единицы. Аналогично сделаем и с башнями нижнего ряда. Каждая дорого соединяет две различные башни напрямую. Известно, что никакие две дороги не пересекаются. Более формально это можно записать следующим образом. Для дороги, которая соединяет башню $i$ верхнего ряда и башню $j$ нижнего, нельзя найти дорогу, которая соединяет башни $k$ и $l$, такую, что $i$ > $k$ и $j$ < $l$, или такую, что $i$ < $k$ и $j$ > $l$. Вам необходимо найти пару башен такую, что сумма их стоимостей максимальна и они не соединены дорогой.

В первой строке дано три числа $n$, $m$, $k$ ($1 \le n, m \le 10^5, 0 \le k \le 10^5$) --- количество башен в верхнем ряду, количество башен в нижнем ряду и количество дорог. В следующих $k$ строках находится по два числа $a$ и $b$ ($1 \le a \le n$, $1 \le b \le m$), которые обозначают, что существует дорога между башней $a$ верхнего ряда и башней $b$ нижнего. В следующей строке записано число $t$ ($1 \le t \le 100$) --- количество различных наборов стоимостей башен. Каждый набор характеризуется четверкой чисел $a$, $b$, $c$, $d$ ($1 \le a, b, c, d \le 10^6$). Она обозначает следующее. Стоимость первой башни первого ряда ровна $a$. Пусть стоимость $i$-й башни ровна $c_i$, тогда стоимость $i$ + 1 ровна ($c_i \cdot b + c) \% d$. Будем считать, что после последней башни верхнего ряда следует первая башня нижнего ряда.

Для каждого набора стоимостей необходимо вывести в отдельной строке два числа --- номера башен из вернего и нижнего ряда, которые удовлетворяют условию. Если же таких башен не существует выведите в этой строке -1. Если существует несколько ответов, которые удовлетворяют условию, можете вывести любой.