3383: 小W 学物理

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:外部导入
提交:4 解决:1

题目描述

为了测试小W 的物理水平,Mr.X 在二维坐标系中放了N 面镜子(镜子坐标绝对值不超 过M),镜子均与坐标轴成45°角,所以一共有两种类型“/”和“\”。原点不会有镜子,任 意一点最多只有一面镜子。 镜子两个面都能反光,而中间不透光,例如,对于一个“/”型镜子,下方向射入的光 线会被反射到右方向,左方向射入的光线会被反射到上方向。 现在有一条光线从原点沿X 轴正方向射出,求走过T 路程后所在位置。

输入

第一行三个整数N,M,T。 第2 到N+1 行,每行两个整数Xi,Yi,表示镜子坐标,一个字符Si 表示镜子类型。

输出

一行两个整数,表示走过T 路程后的坐标。

样例输入 复制

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

样例输出 复制

3 1

提示

【数据规模】

对于20%的数据:N=1

对于40%的数据:N<=1000

对于40%的数据:M<=2000

对于40%的数据:T<=1000000

对于100%的数据N<=100000,M<=1000000000,T<=10^18