Bài tập

Cho một mảng gồm \(N\) phần tử nguyên. Nhiệm vụ của bạn là thực hiện các truy vấn thuộc một trong ba loại sau:

• 1 a b x --- Cộng thêm \(x\) vào tất cả các phần tử trong đoạn \([a, b]\).
• 2 a b x --- Gán tất cả các phần tử trong đoạn \([a, b]\) bằng \(x\).
• 3 a b --- In ra tổng các phần tử trong đoạn \([a, b]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N, Q \leq 2 \cdot 10^5)\) --- số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq 10^6)\) --- các phần tử ban đầu của mảng.

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong ba định dạng sau:

• 1 a b x \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).

• 2 a b x \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
• 3 a b \((1 \leq a \leq b \leq N)\).

Output

Với mỗi truy vấn loại 3, in ra một dòng chứa tổng các phần tử trong đoạn \([a, b]\) tại thời điểm đó.

Example

6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5

7
11
15

Scoring

• Subtask 1 (25% số điểm): \(N, Q \leq 2000\).
• Subtask 2 (25% số điểm): Không có truy vấn loại \(2\).
• Subtask 3 (25% số điểm): Không có truy vấn loại \(1\).
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Nhóm bạn thân của Minh gồm \(n\) người. Mỗi người trong nhóm sống tại một địa điểm khác nhau trong thành phố, được biểu diễn dưới dạng hệ tọa độ \(O(x, y)\). Người bạn thứ \(i\) sống tại tọa độ \((x[i], y[i])\).

Nhân dịp sinh nhật Minh, nhóm quyết định tổ chức một buổi tiệc tụ họp tại một địa điểm bất kì trong thành phố. Để đảm bảo mọi người có thể dễ dàng di chuyển, cả nhóm muốn chọn vị trí sao cho tổng khoảng cách cần phải di chuyển từ nhà của mọi người đến điểm đó là nhỏ nhất.

Khoảng cách giữa hai điểm \((x_1, y_1)\) và \((x_2, y_2)\) được tính theo công thức:

Bạn hãy tìm ra vị trí thỏa mãn mong muốn trên nhé.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^5)\), số lượng bạn bè.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x[i]\), \(y[i]\) \((0 \le x[i], y[i] \leq 10^9)\), biểu diễn tọa độ của người bạn thứ \(i\).

Output

In ra tổng khoảng cách nhỏ nhất mà mọi người cần di chuyển để cùng đến được một điểm bất kì.

Example

3
3 2
2 2
1 0

4

Scoring

• Có \(30\%\) số test ứng với \(n, x[i], y[i] \le 100\)
• Có \(20\%\) số test ứng với \(x[i], y[i] \le 1000\)
• \(50\%\) số test còn lại không có ràng buộc gì thêm.

Vân có \(N\) đồ trang sức trên kệ được đánh số \(1, 2, \ldots, N\) từ trái sang phải. Đồ trang sức có nhiều loại khác nhau, được biểu thị bằng số nguyên dương. Món đồ thứ \(i\) trên kệ là loại \(A_i\).

Hôm nay Vân sẽ bay ra nước ngoài gặp gia đình và muốn mang theo càng nhiều đồ trang sức càng tốt. Tuy nhiên, vì đang vội nên Vân phải lấy một khoảng đồ trang sức liên tiếp trên kệ. Nghĩa là Vân sẽ chọn hai chỉ số, \(l\) và \(r\), và lấy tất cả các món đồ trang sức được đánh số \(l, l + 1, \ldots, r - 1, r\). Ngoài ra, do các quy tắc về thuế, an ninh sân bay sẽ vứt bỏ tất cả các loại đồ trang sức mà Vân có nhiều hơn \(S\) món trong đồ mang theo.

Ví dụ: giả sử \(S = 2\), Vân mang theo sáu món đồ trang sức: một loại \(0\), hai loại \(1\) và ba loại \(2\). Vân sẽ mất tất cả các nữ trang loại \(2\) ở sân bay!

Yêu cầu: Hãy giúp Vân chọn \(l\) và \(r\) sao cho cô ấy có thể mang được nhiều đồ trang sức nhất cho gia đình mình.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T \leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:
• Dòng một chứa hai số nguyên dương \(N\) và \(S\) (\(S \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 10^5\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là số đồ trang sức tối đa mà Vân có thể mang ra nước ngoài thăm gia đình.

Example

1
6 2
1 1 4 1 4 4

4

Scoring

\begin itemize

• Subtask \(1\) (15 điểm): \(N \le 300\).
• Subtask \(2\) (15 điểm): \(N \le 1000\).
• Subtask \(3\) (70 điểm): Không có ràng buộc nào khác.
  \end itemize

Cho hai dãy số nguyên dương độ dài \(n\):
\(a=(a_1,a_2,\dots,a_n)\) và \(b=(b_1,b_2,\dots,b_n)\). Biết rằng các phần tử của hai dãy đều là các số nguyên dương thuộc tập \(\{1,2,\dots,n\}\).

Ta định nghĩa một phép biến đổi như sau: chọn hai chỉ số \(i\) và \(j\) thỏa \(1\le i\le j\le n\), rồi hoán đổi hai đoạn con
$
a_i,a_{i+1},\dots,a_j
\quad\text{và}\quad
b_i,b_{i+1},\dots,b_j
$
giữa hai dãy. Sau phép hoán đổi thu được hai dãy mới:
$
a' = (a_1,\dots,a_{i-1},\,b_i,\dots,b_j,\,a_{j+1},\dots,a_n),
$
$
b' = (b_1,\dots,b_{i-1},\,a_i,\dots,a_j,\,b_{j+1},\dots,b_n).
$

Nếu sau khi thực hiện phép biến đổi như trên có ít nhất một trong hai dãy \(a'\) hoặc \(b'\) là một hoán vị của tập \(\{1,2,\dots,n\}\) thì ta nói phép biến đổi đó tạo ra một hoán vị trộn.

Yêu cầu: Với mỗi test, hãy xác định có bao nhiêu cặp \((i,j)\) khác nhau sẽ tạo ra hoán vị trộn theo định nghĩa trên.

\InputFile

• Dòng đầu tiên là số nguyên \(t\) (\(t\le 5\)) --- số test.

• Mỗi test gồm ba dòng:

• Dòng đầu của test chứa số nguyên \(n\) (\(1\le n \le 2\cdot 10^5\)).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\) (mọi \(a_i \le n\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1,b_2,\dots,b_n\) (mọi \(b_i \le n\)).

\OutputFile

• Ghi ra \(t\) dòng, mỗi dòng là một số nguyên --- số cách (số cặp \((i,j)\) khác nhau) có thể tạo ra hoán vị trộn cho test tương ứng.

\Scoring

• Subtask 1 (30%): \(n \le 100\).
• Subtask 2 (30%): \(n \le 5000\).
• Subtask 3 (40%): không có ràng buộc gì thêm.

Example

2
6
3 2 1 4 4 5
2 3 3 4 6 5
2
1 2
1 2

8
3