题目描述

疯狂戴夫在玩植物大战僵尸卡牌游戏，他的卡组里混入了两张特殊卡牌：樱桃炸弹和坚果墙。

一共有 $n(n \ge 2)$ 张牌。初始樱桃炸弹在第 $X$ 张，坚果墙在第 $Y$ 张。戴夫会对卡组进行 $m$ 次洗牌操作，每次洗牌选定三个整数 $a_i,b_i,c_i$，将卡组中序号在二进制表示下是 $a_i$ 子集并且是 $b_i$ 超集 的牌按序号从小到大依次取出，把取出的牌向前轮换一次之后再按顺序放回之前取出牌的所有位置，重复这个过程进行 $c_i$ 次。

现在你知道了这 $m$ 次洗牌的参数，请你确定最终这两张特殊卡牌的位置。

定义：如果一个数 $x$ 每一个二进制下为 $1$ 的数位在 $y$ 中也为 $1$，而 $y$ 中还可能有其他数位为 $1$， 则称 $x$ 为 $y$ 的子集，$y$ 为 $x$ 的超集。

换言之，对于子集和超集的关系：

• 子集：$x \subseteq y$ 当且仅当 $(x \text{ & } y) = x$，即 $x$ 的所有二进制位都在 $y$ 中出现
• 超集：$y \supseteq x$ 当且仅当 $(x \text{ & } y) = x$，即 $y$ 包含 $x$ 的所有二进制位
• 例如：$5 = (101)_2$ 是 $7 = (111)_2$ 的子集，因为 $5 \text{ & } 7 = 5$
• 例如：$7 = (111)_2$ 是 $5 = (101)_2$ 的超集，因为 $5 \text{ & } 7 = 5$

输入格式

第一行四个正整数 $n, X, Y,m$ 含义如题面所述。

接下来 $m$ 行每行三个整数 $a_i,b_i,c_i$ 表示每次洗牌参数。

输出格式

输出一行两个正整数分别表示樱桃炸弹和坚果墙洗牌结束后的位置。

样例 1

4 1 2 3
3 0 1
5 0 2
4 0 3

3 1

样例解释 1

第一轮洗牌取出了第 $1 \sim 3$ 张，向前轮换一次后，樱桃炸弹在第 $3$ 张，坚果墙在第 $1$ 张。

第二轮取出第 1 张和第 4 张，轮换两次不变。

第三轮只取出了第 4 张，轮换三次后不变。

样例 2

见选手目录下的 ex_shuffle/ex_shuffle2.in 与 ex_shuffle/ex_shuffle2.out。

数据范围与提示

对于所有测试数据，$n\ge 2,\ n,m \le 200000,\ 1 \le X,Y \le n$ 且 $X \not = Y$, $0 \le a_i,b_i,c_i < 2^{30}$。

每个测试点的具体限制见下表：

\begin{array}{|c|c|c|c|} \hline \textbf{测试点编号} & n \le & m \le & \textbf{特殊限制} \\ \hline 1\sim 8 & 100 & 100 & \textbf{无} \\ \hline 9\sim 12 & 200000 & 200000 & c_i = 1 \\ \hline 13\sim 14 & 200000 & 200000 & a_i = b_i \\ \hline 15\sim 17 & 200000 & 200000 & a_i \le n \\ \hline 18\sim 20 & 200000 & 200000 & \textbf{无} \\ \hline \end{array}