时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
「你要去哪里」
鸥「……」
「我记得，你的本体，现在应该是在外国对吧」
「你是要回那里去吗」
鸥「……」
鸥「不是的」
鸥慢慢地摇了摇头。 然后，望向了天空。望向了，那闪耀着无数繁星的，那无比遥远的天空。鸥「是一个更加——」
鸥「遥远的地方」
「更加遥远的地方……？」
天空中，n 颗星星构成了一个序列，第 i 颗星有一个属性 ai。
久岛鸥需要回答，来自星空的 m 个询问。
每个询问给出一个区间 [l,r] 和一个正整数 k，鸥需要回答区间内所有星星属性的出现次数中，第 k 大的出现次数是多少，不存在则输出 0。
鸥不会做，于是找到了牛牛。牛牛思考了一会，就会做了。
然而，一些意想不到不到的事情发生了，有些时候，询问会根据上一次的回答而改变，这被称之为“强制在线”。
于是，牛牛不会了，然后就找到了你，希望你能够协助解决这个问题。
输入描述:
第一行三个正整数 n,m 和 type，分别表示星星序列长度、询问次数和强制在线参数。
接下来一行 n 个正整数，其中第 i 个正整数表示序列中的第 i 个数 ai。接下来 m 行，每行三个整数 l,r 和 k，表示一次询问。若强制在线参数 type=1 则实际询问的 l',r' 和 k' 由输入的 l,r 和 k 经以下运算得到：l' = l xor lastansr' = r xor lastansk' = k xor lastans其中 xor 为按位异或运算，lastans 为上次询问的答案，初始时 lastans=0。
输出描述:
共 m 行，每行输出一个整数表示你的答案。
示例1