Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem. You are given an array a consisting of n positive integers and queries to it. The queries can be of two types: Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner: a l , a l + 1, ..., a r - 1, a r → a r , a l , a l + 1, ..., a r - 1. Count how many numbers equal to k are on the segment from l to r (both borders inclusive). Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it? The first line contains integer n ( 1 ≤ n ≤ 10 5 ) — the number of elements of the array. The second line contains n integers a 1, a 2, ..., a n ( 1 ≤ a i ≤ n ). The third line contains a single integer q ( 1 ≤ q ≤ 10 5 ) — the number of queries. The next q lines contain the queries. As you need to respond to the queries online, the queries will be encoded . A query of the first type will be given in format: 1 l ' i r ' i . A query of the second type will be given in format: 2 l ' i r ' i k ' i . All the number in input are integer. They satisfy the constraints: 1 ≤ l ' i , r ' i , k ' i ≤ n . To decode the queries from the data given in input, you need to perform the following transformations: Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0 ). If after transformation l i is greater than r i , you must swap these values. For each query of the 2-nd type print the answer on a single line.