Serega 喜欢乐趣。然而,每个人都以独特的方式享受乐趣。 Serega 通过解决查询问题获得乐趣。有一天,Fedor 想到了这样一个问题。
给定一个由 n 个正整数组成的数组 a 并对其进行查询。查询可以有两种类型:
1. 在从 l 到 r(包括两个边界)的段上向右进行单位循环移位。即按以下方式重新排列数组的元素方式:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1]。
2. 计算从l到r(包括两个边界)的线段上有多少个等于k的数字。
Fedor 急忙去看 Serega 享受这个问题,Serega 很快就解决了。来看看你能解决吗?
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 数组元素的数量。第二行包含 n 个整数 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n)。
第三行包含一个整数 q (1 ≤ q ≤ 105) — 查询数量。接下来的 q 行包含查询。
由于您需要在线回复查询,查询将会被编码。第一种类型的查询将以以下格式给出:1 l'i r'i。第二种类型的查询将以以下格式给出:2 l'i r'i k'i。输入的所有数字均为整数。它们满足约束条件:1 ≤ l'i、r'i、k'i ≤ n。
要根据输入中给出的数据解码查询,您需要执行以下转换:
li = ((l'i +lastans - 1) mod n) + 1; ri = ((r'i + Lastans - 1) mod n) + 1; ki = ((k'i + Lastans - 1) mod n) + 1。
其中lastans是对第二类型查询的最后回复(最初,lastans = 0)。如果转换后 li 大于 ri,则必须交换这些值。
输出
对于第二类型的每个查询,将答案打印在一行上。
示例
输入 #1
7 6 6 2 7 4 2 5 7 1 3 6 2 2 4 2 2 2 4 7 2 2 2 5 1 2 6 1 1 4 2 1 7 3
输出 #1
2 1 0 0
输入 #2
8 8 4 2 2 7 7 8 8 8 1 8 8 2 8 1 7 1 8 1 1 7 3 2 8 8 3 1 1 4 1 2 7 1 4 5
输出 #2
2 0