N개의 정수로 이루어진 수열 A가 주어집니다. 이 수열에는 같은 값이 여러 개 존재할 수 있습니다.

이 수열을 기반으로 특정 조건을 만족하는 원소가 총 몇 개인지 조사하는 Q개의 질의(Query)를 처리해야 합니다.

수열의 초기 원소들이 주어지고, 이어서 Q개의 질의가 주어질 때 각 질의의 타입에 맞는 정확한 원소의 개수를 출력하는 프로그램을 작성하시오.

질의의 타입은 다음과 같이 5가지로 주어집니다:

• 1 X : 수열의 원소 중 X 이상인 원소의 총 개수를 출력한다. (원소 ≥ X)
• 2 X : 수열의 원소 중 X 초과인 원소의 총 개수를 출력한다. (원소 > X)
• 3 X : 수열의 원소 중 X 이하인 원소의 총 개수를 출력한다. (원소 ≤ X)
• 4 X : 수열의 원소 중 X 미만인 원소의 총 개수를 출력한다. (원소 < X)
• 5 L R : 수열의 원소 중 구간 [L, R] 내에 존재하는 원소의 총 개수를 출력한다. (L ≤ 원소 ≤ R)

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)과 질의의 개수 Q (1 ≤ Q ≤ 100,000)가 공백을 사이에 두고 주어진다.

둘째 줄에는 수열 A를 구성하는 N개의 정수가 공백을 사이에 두고 주어진다. 각 원소는 0 이상 1,000,000,000 이하의 정수이다.

셋째 줄부터 Q개의 줄에 걸쳐 질의가 주어진다. 각 질의는 타입 인자1 (인자2) 형식으로 주어지며, 입력되는 모든 정수 인자는 0 이상 1,000,000,000 이하이다.

(타입 5의 경우 항상 L ≤ R 임이 보장된다.)

출력

Q개의 줄에 걸쳐, 각 질의에 대한 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

7
7
3
8
6
6