描述

注:坐标平面没有边缘,光线不会因为碰到边界而中途停下,m的意义是所有镜子坐标绝对值的最大值不会超过m。

从前有一个坐标网格(其中坐标的绝对值不会超过m)。从左到右x坐标逐渐增加,而从下到上y坐标逐渐增加。

在网格中摆放着n面镜子,第i面镜子的坐标为(x[i],y[i])。镜子均与坐标轴成45°角。所以共有两种类型的镜子:“\”型和“/”型。特殊地,原点处不会有任何镜子,也不会有某个位置有多面镜子。

镜子的两个面都能够反射光线,而中间不透光,例如,对于一个“/”型镜子,从下面射入的光线会被反射到右方向,而从左面射入的光线会被反射到上方向。

现有一条光线从原点所在格子沿x轴正方向射出,求它走过$T$格路程后所在的位置。

输入格式

第一行为三个正整数n,m,T,分别代表镜子的个数与坐标的范围。

接下来n行,每行两个整数和一个字符x[i],y[i],t[i],代表某个镜子的位置和类型。

输出格式

输出两个整数,分别代表走过T格路程后的x坐标和y坐标。

样例输入

5 2 8
0 1 \
0 2 /
1 0 /
1 1 \
1 2 \

样例输出

3 1

数据范围与约定

存在10%的数据,n=1。

存在40%的数据,n≤1,000。

存在40%的数据,m≤1,000。

存在40%的数据,T≤1,000,000。

对于100%的数据,n≤100,000,m≤1,000,000,000,T≤10^{18}。

具体地,数据范围如下表所示:

测试点编号 n m T
1 =1 ≤1,000 ≤100,000
2,3   ≤1,000 ≤100,000
4,5 ≤1,000   ≤100,000
6,7 ≤1,000 ≤1,000  
8 =1    
9,10 ≤1,000    
11,12,13   ≤1,000  
14,15,16     ≤100,000
17,18,19,20      

样例解释

在8个单位时间的路线是:右上左上右下右右。