Statement is not available in English language
J. Шахматное собеседование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На собеседовании в одну крупную авиакомпанию в качестве испытания кандидату предлагают сыграть в особые шахматы. Здесь шахматное поле представлено в виде неориентированного графа, состоящего из $$$n$$$ вершин, соединенных $$$m$$$ ребрами двух цветов — белого и черного. В вершинах с номерами $$$k$$$ и $$$q$$$ расположены фигуры короля и ферзя соответственно. Кандидат может выбрать, за какую фигуру он будет играть, а собеседующий выберет оставшуюся. Игроки выполняют ходы поочередно, первым ходит игрок, играющий за фигуру $$$X$$$. За один ход король может перемещаться в любую вершину, соединенную ребром с текущей, а ферзь может перемещаться в любую вершину, до которой существует путь из текущей вершины, состоящий из ребер одного цвета. Побеждает игрок, после хода которого фигуры оказались в одной вершине. Если побеждает кандидат, то собеседование считается пройденным.

Теперь вы интересуетесь для некоторых конфигураций игры $$$k$$$, $$$q$$$ и $$$X$$$, за какую фигуру нужно играть, чтобы гарантировать победу и, естественно, успешное прохождение собеседования.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке набора входных данных задано три целых числа $$$n$$$, $$$m$$$ и $$$l$$$ ($$$2 \le n \le 100$$$, $$$1 \le m \le 100$$$, $$$1 \le l \le 5 \cdot 10^5$$$) — количество вершин в графе, ребер и количество конфигураций игры соответственно.

В следующих $$$m$$$ строках задано по 3 целых числа $$$u$$$, $$$v$$$ и $$$c$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$c \in \{1, 2\}$$$) — номера вершин, соединенных ребром, и цвет ребра. Гарантируется, что граф состоит из одной компоненты связности и не содержит кратных ребер.

В следующих $$$l$$$ строках задано два целых числа $$$k$$$ и $$$q$$$ ($$$1 \le k, q \le n$$$, $$$k \ne q$$$) и строка $$$X$$$ — номера вершин, где расположены король и ферзь, и название фигуры, которая должна выполнить первый ход. Если задано «queen» (без кавычек), то первым ходит игрок, играющий за ферзя, если «king» (без кавычек) — игрок, играющий за короля.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$100$$$, а сумма $$$l$$$ не превышает $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных для каждой конфигурации игры выведите «king» (без кавычек), если кандидат должен выбрать короля, чтобы гарантировать победу, «queen» (без кавычек), если кандидат должен выбрать ферзя, и «draw» (без кавычек), если кандидат не сможет гарантировать победу, играя за одну из фигур.

Пример
Входные данные
2
4 4 2
1 2 1
2 3 2
3 4 1
4 1 2
1 3 king
1 3 queen
6 6 1
1 2 1
2 3 2
3 4 1
4 5 2
5 6 1
6 1 2
1 3 queen
Выходные данные
queen
king
draw