Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P178PROL - ROUND 8L - TRUY VẤN

 

Cho dãy số A gồm N phần tử và dãy số B gồm M phần tử, trong đó B[j] = j.
Có 3 loại truy vấn như sau:
 1 k V: Thay đổi phần tử A[k] = V.
 2 S1 S2: Yêu cầu đếm số lượng bộ (i, j) thỏa mãn S1 <= A[i] + B[j] <= S2.
 3 L R: Đảo thứ tự các phần tử trong mảng B trong đoạn L  R.

Cho dãy số A gồm N phần tử và dãy số B gồm M phần tử, trong đó B[j] = j.

Có 3 loại truy vấn như sau:

 1 k V: Thay đổi phần tử A[k] = V.

 2 S1 S2: Yêu cầu đếm số lượng bộ (i, j) thỏa mãn S1 <= A[i] + B[j] <= S2.

 3 L R: Đảo thứ tự các phần tử trong mảng B trong đoạn L --> R.

 

Input

Dòng đầu tiên gồm 3 số N, M, Q trong đó Q là số lượng truy vấn.

Dòng tiếp theo gồm N phần tử của dãy số A[].

Q dòng tiếp theo, mỗi dòng là một truy vấn.

1 <= N, M, Q <= 10^5.

1 <= A[i], V <= 10^5.

1 <= S1, S2 <= 2*10^5

Output

Với truy vấn loại 2, hãy in ra đáp số trên một dòng.

Example

Input:
4 5 5
1 2 1 1
3 2 4
2 6 8
1 3 5
2 6 8
2 6 9 Output: 5
7
8
Giải thích test:
Dãy số A ban đầu: 1 2 1 1
Dãy số B ban đầu: 1 2 3 4 5
Truy vấn 1: Đổi dãy B thành 1 4 3 2 5
Truy vấn 2: Có 5 cặp (i, j) thỏa mãn là (1,5), (2, 2), (2, 5), (3, 5), (4, 5).

Được gửi lên bởi:adm
Ngày:2017-04-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.