时间限制： 1.0 秒

空间限制： 512 MB

题目描述

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

现在有一个 $N \times M$ 的棋盘，棋盘上有 $K$ 个小葱。第 $i$ 个小葱在棋盘的第 $x_i$ 行第 $y_i$ 列。在每单位时间内，每个小葱会朝着当前自己面朝的方向在棋盘上走一格；如果当前在棋盘边缘且走一格会走出棋盘的话，则小葱会将自己的方向转一百八十度。（注意这个单位时间内小葱会只旋转不进行移动）如果在某个时刻，有任何两个小葱处于同一个格子，那么这个时候便会发生战争。第 $i$ 个小葱的战斗力为 $f_i$，如果同一时刻有多个小葱在同一个格子，那么战争之后只会留下战斗力最高的小葱，剩下的小葱都会在原地枯萎，之后将不再移动。现在小葱同学希望知道按照以上的规则，在时刻 $t$ 的时候所有小葱的位置，请你帮助他完成这个任务。

输入格式

从标准输入读入数据。

第一行三个数 $N,M,K$ 代表棋盘的行数、列数和小葱的个数。

接下来 $K$ 行每行三个数 $x_i, y_i, d_i, f_i$ 表示每个小葱一开始所在的行、列、面朝的方向以及战斗力。其中 $d_i$ 只可能是 $0, 1, 2, 3$ 中的一个，分别代表上下左右四个方向。

最后一行一个整数 $t$，代表结束的时刻。

输出格式

输出到标准输出。

$K$ 行每行两个数，代表每棵小葱在时刻 $t$ 的时候所在的位置。

3 3 3
1 1 1 1
2 2 2 2
3 3 3 3
4

2 1
2 3
3 1

样例 1 解释

在第一时刻，第一棵小葱和第二棵小葱均走到了第二行第一列的位置，此时发生战争，第一棵小葱枯萎。在第二时刻，第二棵小葱发现前方无法再走，所以此时进行旋转，方向变为向右。

子任务

对于所有数据，保证 $1 \le N, M \le 100,~1 \le K \le 1000,~1 \le x_i \le N,~1 \le y_i \le M,~1 \le f_i \le 1000,~0 \le d_i \le 3,~0 \le t \le 1000$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（20 分）：$M=1$；
• 子任务 2（20 分）：$d_i=0,1$；
• 子任务 3（20 分）：$t\le 10$；
• 子任务 4（20 分）：$k\le 10$；
• 子任务 5（20 分）：无额外限制。