Cánh đồng hoa ở Amsterdam được chia thành $N$ ô đất, mỗi ô đất được đánh số từ $1$ đến $N$.
Hai người làm vườn chăm chỉ low_ và lantrungseo được giao chăm sóc hoa trên những ô đất này. Vì là những người làm vườn yêu bộ môn giải thuật, đồng thời cũng vì có quá nhiều hoa màu, low_ và lantrungseo đã cùng đưa ra bài toán như sau:
Ban đầu trên ô đất thứ $i$ có $A_i$ bông hoa. Mỗi ngày, hai người làm vườn sẽ phải thực hiện một trong hai sự kiện sau theo danh sách cho trước:
"_1_": Chọn ra hai chỉ số $l, r$ ($1 <= l <= r <= N$). Với mỗi $i$ thuộc đoạn $[ l, r ]$, trồng trên ô đất thứ $i$ số lượng hoa là $i -l + 1$. Ví dụ, nếu $N = 5$ và chọn $l = 2$ và $r = 4$, thì trồng 1 bông trên ô đất 2, 2 bông trên ô đất 3, 3 bông trên ô đất 4.
"_2_": Hai người làm vườn chán trồng hoa (nên sẽ không trồng thêm bông nào ngày hôm đó). Thay vì đó, low_ đố lantrungseo tính tổng số bông hoa trên các ô đất thuộc đoạn $[ u, v ]$ ($1 <= u <= v <= N$).
Bạn có danh sách các sự kiện diễn ra trong $Q$ ngày. Hãy giúp lantrungseo trả lời các sự kiện "_2_".
Dòng đầu chứa $T$ ($1 <= T <= 4$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:
- Dòng đầu chứa $N$ ($1 <= N <= 10^5$) - số ô đất trên cánh đồng hoa.
- Dòng thứ hai chứa $N$ số: $A_1, A_2,..., A_N$. ($0 <= A_i <= 10^6$) - số bông hoa trên từng cánh đồng.
- Dòng thứ 3 chứa $Q$ ($1 <= Q <= 10^5$) - số sự kiện diễn ra trên cánh đồng.
- $Q$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:
+ "_1_": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $l, r$ cách nhau bởi một dấu cách ($1 <= l <= r <= N$).
+ "_2_": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $u, v$ cách nhau bởi một dấu cách ($1 <= u <= v <= N$).
Với mỗi sự kiện "_2_", in ra một số duy nhất là kết quả của sự kiện.
20% số điểm ứng với $N <= 1000, Q <= 1000$.
40% số điểm ứng với $N <= 10^5, Q <= 10^5$. Trong mỗi bộ test, truy vấn _"1"_ cuối cùng sẽ xuất hiện trước truy vấn _"2"_ đầu tiên.
40% số điểm còn lại ứng với giới hạn gốc.
Bộ test thứ nhất:
Ban đầu: $2, 1, 3, 5, 2$
Sau ngày đầu tiên: $3, 3, 6, 5, 2$
Sau ngày thứ ba: $3, 3, 6, 6, 4$
Sau ngày thứ tư: $3, 4, 8, 9, 8$
Sau ngày thứ năm: $4, 4, 8, 9, 8$
## Input
Dòng đầu chứa $T$ ($1 <= T <= 4$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:- Dòng đầu chứa $N$ ($1 <= N <= 10^5$) - số ô đất trên cánh đồng hoa.- Dòng thứ hai chứa $N$ số: $A_1, A_2,..., A_N$. ($0 <= A_i <= 10^6$) - số bông hoa trên từng cánh đồng.- Dòng thứ 3 chứa $Q$ ($1 <= Q <= 10^5$) - số sự kiện diễn ra trên cánh đồng.- $Q$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:+ "_1_": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $l, r$ cách nhau bởi một dấu cách ($1 <= l <= r <= N$).+ "_2_": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $u, v$ cách nhau bởi một dấu cách ($1 <= u <= v <= N$).
## Output
Với mỗi sự kiện "_2_", in ra một số duy nhất là kết quả của sự kiện.
[samples]
## Scoring
20% số điểm ứng với $N <= 1000, Q <= 1000$.40% số điểm ứng với $N <= 10^5, Q <= 10^5$. Trong mỗi bộ test, truy vấn _"1"_ cuối cùng sẽ xuất hiện trước truy vấn _"2"_ đầu tiên.40% số điểm còn lại ứng với giới hạn gốc.
## Note
Bộ test thứ nhất:Ban đầu: $2, 1, 3, 5, 2$Sau ngày đầu tiên: $3, 3, 6, 5, 2$Sau ngày thứ ba: $3, 3, 6, 6, 4$Sau ngày thứ tư: $3, 4, 8, 9, 8$Sau ngày thứ năm: $4, 4, 8, 9, 8$
**Definitions**
Let $ (x_0, y_0) \in \mathbb{R}^2 $ be Dahlia’s position.
Let $ R \in \mathbb{Z}^+ $ be the maximum pull distance.
Let $ T = \{ (x_i, y_i) \in \mathbb{R}^2 \mid i \in \{1, \dots, N\} \} $ be the set of $ N $ target positions, with $ (x_i, y_i) \neq (x_0, y_0) $ for all $ i $, and all targets distinct.
**Constraints**
1. $ |x_0|, |y_0| \leq 10^9 $
2. $ 1 \leq R \leq 10^9 $
3. $ 1 \leq N \leq 5 \times 10^5 $
4. $ (x_i, y_i) \neq (x_0, y_0) $ for all $ i $, and $ (x_i, y_i) \neq (x_j, y_j) $ for all $ i \neq j $
**Objective**
Count the number of targets $ (x_i, y_i) \in T $ such that the Euclidean distance from $ (x_0, y_0) $ to $ (x_i, y_i) $ is at most $ R $:
$$
\left| \left| (x_i - x_0, y_i - y_0) \right| \right|_2 \leq R
$$