You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

出题人 yummy ： 我是真不会给题起中文名啊！！

题目描述

小 E 和小 F 在玩一个游戏。在一局游戏开始前，他们分别有 $P$ 点体力和 $B$ 点血量。

他们每人有 $n$ 个技能。每个技能的描述均为“消耗 $p$ 点体力并让对方血量减少 $b$”。显然，如果技能的使用者现有体力少于 $p$，则无法使用该技能。

游戏开始后有若干个回合。每个回合小 E 先使用不超过一个技能，然后小 F 使用不超过一个技能，最后两人的体力都加上 $d$。（如果加上 $d$ 之后体力超过上限值 $P$，则体力变成 $P$。）

如果某一回合一个玩家发动技能后，对方的血量不超过 $0$，那么对方死亡，该玩家获胜。

假如两人均采用最优策略（能获胜尽量获胜，否则尽量让对方多扣血），给出两人所拥有的所有技能，判断谁能获胜，以及获胜方最后剩下的血量。

输入格式

本题有多组数据。

输入的第一行有且仅有一个正整数 $T$。

之后的每组数据中：

第 $1$ 行共四个正整数 $n,P,B,d$，表示技能个数、初始体力、初始血量和体力的回合增量。

第 $2\sim n+1$ 行，每行两个正整数 $p,b$ 表示小 E 的一个技能。

第 $n+2 \sim 2\times n+1$ 行，每行两个正整数 $p,b$ 表示小 F 的一个技能。

输出格式

对于每组数据：

• 如果小 E 获胜，则输出 E x，其中 $x$ 为小 E 最后的血量。
• 如果小 F 获胜，则输出 F x，其中 $x$ 为小 F 最后的血量。
• 如果游戏无法结束，则输出 T。

样例 #1

样例输入 #1

2
2 5 10 2
4 5
3 4
1 4
6 100
2 5 100 0
4 5
1 10
1 19
6 200

样例输出 #1

E 2
T

提示

【样例解释】

第一组数据中，两人初始时有 $5$ 体力和 $10$ 血量。

小 E 手上有两个技能：一个耗费 $4$ 体力扣对方 $5$ 血量，另一个耗费 $3$ 体力扣对方 $4$ 血量。

小 F 手上有两个技能：一个耗费 $1$ 体力扣对方 $4$ 血量，另一个耗费 $6$ 体力扣对方 $100$ 血量。（显然技能 $2$ 不可能发挥作用。）

一种可能的对战方式如下：

• 第一回合开始，小 E 率先使用技能 $1$，自己还剩 $1$ 体力，对方还剩下 $5$ 血量。
• 小 F 使用技能 $1$，自己还剩 $4$ 体力，对方还剩下 $6$ 血量。
• 第一回合结束，小 E 增加 $2$ 体力变成 $3$ 体力，小 F 增加 $2$ 体力，但是由于体力槽已满，变成 $5$ 体力。
• 第二回合开始，小 E 放弃使用技能（而非使用 $2$ 技能）以积攒体力。
• 小 F 使用技能 $1$，自己还剩 $4$ 体力，对方还剩下 $2$ 血量。
• 第二回合结束，小 E 增加 $2$ 体力变成 $5$ 体力，小 F 恢复 $5$ 体力。
• 第三回合开始，小 E 使用技能 $1$ 将血量扣成 $0$，游戏结束。

第二组数据中，显然两人把体力耗完也无法把对方血量扣完，所以游戏不可能结束。

【数据范围】

“最多轮数”指最优策略下，游戏在这么多回合内停止。如果留空则不保证一定会停止。

对于全体数据，保证 $1\le T,n\le 10$，$1\le B,b,P,p\le 10^3$，$0\le d\le P$，输入皆为整数。