题目描述

hsez 爆发了魔怔病毒，前线的 Rikka__ 和 ISYRHH 发来捷报，成功摧毁了魔怔始祖 YLCH，不过他们发现 YLCH 遗留了剧毒的魔怔病毒，于是他们向总部的死亡先知 brAKzero 和大魔法师 logfk 发出求助。

brAKzero 通过先知之眼窥探到了魔怔病毒的本质，病毒是一个长为 $n$ 的整数序列，且存在一个魔怔程度 $d$，brAKzero 需要借助大魔法师 logfk 的法力，对病毒进行 $m$ 次操作，病毒才能得到妥善处理。

操作只有一种，形如：type l r，表示判断病毒序列的下标 $l$ 到 $r$ 之间的子区间是否可以重新排序成为公比为 $d$ 的等比数列。

若是，则输出 true，且对这段区间按照大小顺序进行重新排序（$type=1$ 从小到大，$type=2$ 从大到小），否则输出 false​。

输入格式

由于病毒过于复杂，你需要用特殊的方式得到整个序列。

第一行包含三个整数 $n,m,d$。

第二行到第 $n+1$​ 行，每行一个整数 $type$​，若 $type=1$​​，则直接读入，否则再读入两个整数 $x,y$​ 表示第 $i$​ 个数是第 $x$​ 个数乘上 $d^y$​ 的结果。

保证 $x<i$​，且 $type=1$ 时，输入数据的值小于 $10^5$。

第 $n+2$ 行到第 $n+m+1$ 行，每行三个整数 type x y，意义见上文。

输出格式

共 $m$ 行，每行输出 true 或 false 表示每一组操作的答案。

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

true
true
false
true
false

数据规模与约定

对于 $10\%$ 的数据，$m=0$；

对于 $50\%$ 的数据，$1\le n,m\le 10^3$​；

对于另外 $20\%$​ 的数据，保证数据纯随机；

对于 $100\%$ 的数据，$1\le n\le 10^5,1\le m\le 10^6$​ 。

保证序列中的所有数字不重复，保证查询中的 $x\le y$ 。

为了卡掉错误的算法，本题需要保证正解的耗时极小，建议写文件快读或者使用 O2/Ofast 优化。