题目内容

小塔正在玩一个战争棋盘。 棋盘可以视为一个$n$行$m$列的矩阵。小塔初始往棋盘上投放了$k$支军队，每个军队属于不同势力。每回合，小塔可以任选一个军队按"上、下、左、右"四种方向中的一种移动一个方格，会出现以下$4$种情况:

$1$.当这个军队移动到一个未被任何势力占领的格子，则军队移动成功，并将其占领。

$2$.当这个军队移动到自己势力的格子，此时军队移动成功。

$3$.若这个军队将移出地图的边界，将移动失败。该军队原地不动。

$4$.若这个军队将移动到另外一个势力的格子，那么两个势力将发生冲突，拥有较多领土的势力将获胜，并占领对方所有领土，消灭对方的军队。特殊的，若两个冲突的势力领土数量相等，那么势力名字的字典序较大者获胜。如果进攻方获胜，则进攻方移动成功。如果防守方获胜，那么防守方的军队保持原来的位置。

请你在每次移动操作后输出当前操作的结果。

$ps$: 若投放军队的时候有两个或多个军队在同一格子，则直接发生冲突，名字字典序最大的那个势力存活，其他势力消亡。

对于字符串$a$和$b$，我们认为满足以下两个条件中的一种时，$a$的字典序大于$b$: $1$.$b$是$a$的一个前缀，且$a$和$b$不相等。

$2$.对于$a$和$b$中出现的第一个不同的字母，$a$的那个字母的$ascii$值比$b$的那个字母更大。

输入描述

第一行输入三个正整数$n,m,k$，分别代表棋盘的行数、列数，以及势力的数量。

接下来的$k$行，每行输入一个字符串 $str$，以及两个正整数$x$和$y$，代表每个势力的名字，以及初始的坐标为($x,y$)。保证初始投放的军队是没有重名的。 接下来的一行输入一个正整数$q$，代表回合数。

接下来的$q$行，每行输入一个字符串$str$和一个字符$c$，代表即将行动的军队的势力名称，以及行动方向。$c$为'$W$'代表该军队向上走，'$S$'代表向下走，'$A$'代表向左走，'$D$'代表向右走。

数据范围: $1≤n,m≤500$ $1≤k≤min(n×m,2.10^4)$ $1≤x≤n,1≤y≤m$ $1≤q≤2·104$ 保证$str$是长度不超过$10$的、仅包含小写字母的字符串。保证$c$为'$W$'、'$A$'、'$S$'、'$D$'四种字符中的一种。

输出描述

对于每次操作，输出一行答案 若本次移动占领了新的边界。输出一行字符串"$vanquish!$"

若本次移动到了自己的领土，则输出一行字符串"$peaceful$"

若本次由于将移出边界导致移动失败,则输出一行字符串"$out of bounds!$"

若本次移动发生了冲突，胜利者是$xxx$，则输出一行字符串"$xxx wins!$”($xxx$为势力名字)

若输入了不存在的势力，或者输入的字符串代表的势力已经败北，则输出一行字符串"$unexisted empire$."

样例1

输入

3 3 2
ranko 1 1
kotori 2 2
5
ranko D
ranko W
ranko A
kotori W
kotori W

输出

vanquish!
out of bounds!
peaceful.
ranko wins!
unexisted empire. 

说明

第一回合，$ranko$从($1,1$)移动到($1,2$)，占领了一个新格子。

第二回合，$ranko$试图向上移动，但即将出地图边界，移动失败。

第三回合，$ranko$向左返回($1,1$)。

第四回合，$kotori$向上移动到($1,2$)，由于($1,2$)已经被$ranko$占领，两个势力火拼，$ranko$势力范围更大取得胜利，消灭$koroti$并获得其所有领

第五回合，由于$kotori$已经被消灭，所以无法再移动。

样例2

输入

222
abcd 11
abcad 1 2
1
abcd D

输出

abcd wins!

说明

$abcd$的势力向右移动到($1,2$)，和$abcad$势力火拼，两者势力范围相同，但由于"$abcd$"字符串的字典序更大，因此获得胜利。