Background

2024GDKOI pj day1 day2

Description

Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。

该游戏在一颗具有 n 个节点（编号从 1 到 n）的树上进行。

在游戏的开始，Zayin 在节点 a，而 Ziyin 在节点 b。他们轮流操作，Zayin 先移动。在每次移动中，Zayin

能移动到距离当前所在点不超过 da 的节点上，而 Ziyin 能移动到距离当前所在点不超过 db 的节点上（注意可以保持在当前点不动）。当某次移动后，其中一人抓住了另外一人，即移动到了另外一人的节点上，则游戏结束，被抓住的人输掉游戏。

当 Zayin 和 Ziyin 都按最优策略移动的话，谁会是最后赢家呢。

注解：

• 一颗具有 n 个节点的树是指一个具有 n 个节点，n − 1 条边的连通无向图。

• 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。

Format

Input

每个测试点包含多个测试用例。

第一行包含两个整数 d, t，表示测试点编号，和测试用例的数量。每个测试用例的描述如下。

第一行包含两个整数 n, q — 分别为顶点数、询问数。

接下来 n−1 行每行包含两个整数 u, v (1 ≤ u, v ≤ n, u = v)，表示顶点 u 和 v 之间具有一条直接相连的边，保证这些边形成一棵树。接下来 q 行每行包含四个整数 a, b, da, db(1 ≤ a, b, da, db ≤ n) 作为一次游戏，分别表示 Zayin 初始节点、Ziyin 初始节点、Zayin 最大移动距离、Ziyin 最大移动距离

Output

对于每个测试用例的每次游戏，输出一行”Zayin” 或”Ziyin” 表示最后赢家，特别地如果在 10105轮内游 戏没有仍结束，则输出”Draw” 表示平局。

Samples

1 2
6 5
2 3
2 6
2 1
4 3
5 1
5 4 1 2
6 4 4 3
1 4 5 4
5 2 1 4
2 5 1 5
4 5
1 4
3 4
2 4
4 2 2 3
4 3 2 2
4 3 3 3
1 2 1 1
1 2 1 2

Ziyin
Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Draw
Ziyin

Limitation

保证所有测试用例的 n 之和不超过 10^6，q 之和不超过 10^6。