Quadrat Survey (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Given N flower kinds in a row, answer how many flowers of a given kind lie in a range, and remove all flowers in a range on request.

Level: Easy3 of 10
Topics: Array, Simulation
Solved: No attempts yet

Problem

This problem is the same as "Quadrat Survey (Hard)" except for the limits on $N$ and $Q$ .

Sejong is doing a practical assignment on quadrat surveys. A quadrat is a $1\times N$ grid, and its cells are numbered 1 to $N$ in order. Each cell has one flower in bloom. Sejong's world has $10$ billion kinds of flowers, numbered from 1 to $10^9$ by kind. Sejong must count how many flowers of a given kind bloom in a range that his teacher assigns. The teacher changes the ranges often, so Sejong gets annoyed and decides to trample the flowers.

Write a program that handles the following queries for Sejong's assignment.

1 l r k: Print the number of flowers of kind $k$ among the flowers in cells $l$ to $r$ of the quadrat.
2 l r: Sejong tramples the flowers in cells $l$ to $r$ of the quadrat, removing them.

Input

The first line contains a positive integer $N$ , the size of the quadrat. ( $1 \leq N \leq 1\,000$ )

The second line contains $N$ positive integers $A_1, A_2, \cdots, A_N$ , separated by spaces. $A_i$ is the kind of flower in cell $i$ . ( $1 \leq A_i \leq 10^{9}$ )

The third line contains a positive integer $Q$ , the number of queries. ( $1 \leq Q \leq 10\,000$ )

From the fourth line on, each of the $Q$ lines contains one query. ( $1 \leq l \leq r \leq N$ ; $1 \leq k \leq 10^{9}$ )

At least one query of type 1 is given.

Output

For each query of type 1, print the answer on its own line.

Examples1

Example 1

Input

10
1 5 5 5 3 2 1 1 10 2
6
1 1 10 3
1 2 7 5
2 3 5
1 1 3 5
2 4 7
1 1 10 1

Expected output