这个游戏在一个 n 行 m 列的二维棋盘上进行。我们用 来表示第 x 行第 y 列的格子，那么左上角为 ，右下角为。
我们用一个长度为 k 的不重复的坐标的序列（形如) 来表示一条长度为 k 的蛇，其中 称为蛇的头部。在游戏的任何时刻，都满足 k > 1。
游戏开始时，蛇的长度为 1，坐标为 。接下来会进行 q 个操作，每个操作是以下两种类型之一：
l 1 d：蛇的头部往 方向伸长一格，其中 为之一，分别表示 上、下、左、右。
l 2：蛇的尾部缩短一格，保证该操作前蛇的长度大于 1。
棋盘上还有 t 个障碍物，分别位于 ，保证没有两个障碍物占据同一个格子。在任何时候，如果蛇的头部碰到蛇的身体（即蛇的其他格子），或碰到棋盘上的障碍物，或移动到棋盘的边界之外，那么蛇会立即死亡。
输入格式
输入的第一行包含四个非负整数 n, m, t, q具体含义见问题描述。
接下来 t 行，每行两个整数，表示一个障碍物的坐标。保证每个坐标都在棋盘上，即在 (1, 1)到(n,m) 之间，且不存在重复的坐标。