注:坐标平面没有边缘,光线不会因为碰到边界而中途停下,m的意义是所有镜子坐标绝对值的最大值不会超过m.
从前有一个坐标网格(其中坐标的绝对值不会超过m).从左到右x坐标逐渐增加,而从下到上y坐标逐渐增加.
在网格中摆放着n面镜子,第i面镜子的坐标为(x[i]y[i]).镜子均与坐标轴成45°角.所以共有两种类型的镜子:"\"型和"/"型.特殊地,原点处不会有任何镜子,也不会有某个位置有多面镜子.
镜子的两个面都能够反射光线,而中间不透光,例如,对于一个"/"型镜子,从下面射入的光线会被反射到右方向,而从左面射入的光线会被反射到上方向.
现有一条光线从原点所在格子沿x轴正方向射出,求它走过$T$格路程后所在的位置.
第一行为三个正整数nmT,分别代表镜子的个数与坐标的范围.
接下来n行,每行两个整数和一个字符x[i]y[i]t[i],代表某个镜子的位置和类型.
输出两个整数,分别代表走过T格路程后的x坐标和y坐标.
存在40%的数据,n≤1000.
存在40%的数据,m≤1000.
存在40%的数据,T≤1000000.
对于100%的数据,n≤100000m≤1000000000T≤10^{18}.
在8个单位时间的路线是:右上左上右下右右.