Bài tập

Thị trưởng Long sống trong một thành phố gồm \(n\) khu vực dân cư được nối với nhau bởi \(n - 1\) con đường hai chiều,
sao cho từ bất kỳ khu vực nào cũng có thể đi đến mọi khu vực khác.

Long muốn nâng cấp một số con đường để cải thiện tình trạng giao thông. Với mỗi con đường,
ta biết tốc độ di chuyển hiện tại \(v_i\), chi phí nâng cấp \(c_i\) và tốc độ sau khi nâng cấp \(s_i\).

Có \(q\) người dân đến gặp Long với các đề xuất khác nhau.
Đề xuất của người dân thứ \(i\) là:
"Tôi muốn đầu tư \(e_i\) euro để nâng cấp một số con đường trên hành trình từ khu vực \(a_i\) đến khu vực \(b_i\)."

Với mỗi đề xuất, Long muốn biết:
nếu ông chi không quá \(e_i\) euro để chọn nâng cấp một số con đường trên đường đi từ \(a_i\) đến \(b_i\),
thì tốc độ nhỏ nhất trên toàn bộ hành trình này có thể được tăng lên đến bao nhiêu,
trong trường hợp ông lựa chọn nâng cấp tối ưu để tối đa hóa tốc độ nhỏ nhất đó.

\InputFile

Dòng đầu chứa số nguyên \(n\) (\(2 \le n \le 100\,000\)), số khu vực dân cư.

Mỗi dòng trong \(n - 1\) dòng tiếp theo chứa 5 số nguyên \(x_i, y_i, v_i, c_i, s_i\)
(\(1 \le x_i, y_i \le n\), \(1 \le v_i < s_i \le 10^9\), \(1 \le c_i \le 10^9\)),
cho biết khu vực \(x_i\) và \(y_i\) được nối trực tiếp với nhau bằng một con đường có:
tốc độ hiện tại \(v_i\), chi phí nâng cấp \(c_i\), và tốc độ sau nâng cấp \(s_i\).

Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 100\,000\)), số đề xuất của người dân.

Mỗi dòng trong \(q\) dòng tiếp theo chứa ba số nguyên \(a_i, b_i, e_i\)
(\(1 \le a_i, b_i \le n\), \(a_i \ne b_i\), \(1 \le e_i \le 10^{18}\)),
diễn tả đề xuất thứ \(i\).

\OutputFile

Ở dòng thứ \(i\) trong \(q\) dòng, in ra đáp án cho đề xuất thứ \(i\),
tức là tốc độ nhỏ nhất lớn nhất có thể đạt được trên đường đi từ \(a_i\) đến \(b_i\)
nếu chỉ sử dụng tối đa \(e_i\) euro.

\Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 21 &
\(\, n, q \le 1000\)

2 & 29 &
Mỗi khu vực được nối với tối đa 2 khu vực khác

3 & 50 &
Không có ràng buộc bổ sung

\hline
\endtabular
\endcenter

\Examples

\beginexample
\exmp
6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

7
5
11

\exmp
4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10

6
7
5
7

\endexample

\endproblem

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.

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\) và \(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:

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.

Input

• Dòng \(1\): chứa 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 \times 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\)).

Output

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.

Sample Input 1

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

Sample Output 1

8
3