题目描述

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

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

输入格式