← 返回题目列表

Codeforces · 455/D

D. Serega 和乐趣

中文机器翻译题面 查看原题

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