Bài tập

Ngày xửa ngày xưa, trong vương quốc Kỳ Diệu, nhà vua tổ chức một cuộc thi dành cho những chiến binh dũng cảm và thông minh nhất. Nhà vua giao cho các chiến binh một danh sách gồm \(N\) nhiệm vụ để thực hiện, mỗi nhiệm vụ chỉ được hoàn thành khi chiến binh bắt đầu tác vụ từ thời điểm \(l_i\) và hoàn thành tại thời điểm \(r_i\).

Vì độ khó của các nhiệm vụ, các chiến binh không thể đồng thời thực hiện nhiều tác vụ cùng một thời điểm, hay cụ thể là hai nhiệm vụ giao nhau. Hai nhiệm vụ \([l_i, r_i]\) và \([l_j, r_j]\) được gọi là giao nhau nếu tồn tại một thời điểm thuộc cả \(2\) nhiệm vụ trên.

Cuộc thi trên không chỉ là cơ hội tìm kiếm chiến binh mạnh nhất, mà còn là cơ hội để những người "mạnh" về trí não thể hiện khả năng. Cụ thể, nhà vua giao ra bài toán sau, nếu một chiến binh chỉ được làm các nhiệm vụ trong khoảng thời gian từ \(S\) đến \(T\) thì họ có thể hoàn thành tối đa bao nhiêu nhiệm vụ. Nhận thấy bài toán chưa đủ hóc búa, nhà vua bèn chèn thêm một số cập nhật giữa các câu hỏi: thay đổi thời gian của nhiệm vụ \(i\) thành \(U_i\) đến \(V_i\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), là số lượng nhiệm vụ.

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i \le r_i \leq 10^9)\), biểu diễn thời gian bắt đầu và kết thúc của nhiệm vụ thứ \(i\).

• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)), là số lượng yêu cầu mà nhà vua đưa ra.

• Q dòng tiếp theo thuộc một trong \(2\) loại:
  \begin itemize

• \(1 \; i \; u \; v\): Gán \(l_i=u\) và \(r_i=v\).
• \(2 \; S \; T\): Nếu chỉ được phép làm nhiệm vụ trong khoảng thời gian \([S, T]\), thì một chiến binh có thể làm nhiều nhất bao nhiêu nhiệm vụ.
  \end itemize

Output

Xử lý các yêu cầu và đưa ra đáp án cho các câu hỏi của nhà vua.

Example

5
1 5
3 7
2 4
7 10
6 11
4
2 3 10
2 2 10
1 2 11 13
2 1 14

1
2
3

Scoring

Trong tất cả các test:

\(1 \le u \le v \le 10^9\)

\(1 \le S \le T \le 10^9\)

\textbf Cách tính điểm:
\begin itemize

• Có \(15\%\) số điểm ứng với \(n, q \le 20\).
• Có \(15\%\) số điểm ứng với \(n, q \le 10^3\).
• Có \(20\%\) số điểm ứng với \(l_i = r_i\) và \(u = v\).
• Có \(20\%\) số điểm với bộ test không có truy vấn loại \(1\).
• \(30\%\) điểm còn lại không có ràng buộc gì thêm.
  \end itemize

Trong tương lai xa tại hành tinh Binance, Liên minh Thiên hà đã xây dựng một hệ thống mạng lượng tử kết nối \(n\) trạm truyền tin liên hành tinh, các trạm truyền tin được đánh số liên tiếp từ \(1\) đến \(n\) \((1 \leq n \leq 10^5)\). Có \(n - 1\) liên kết kết nối giữa các cặp trạm truyền tin, liên kết thứ \(i\) sẽ kết nối hai trạm truyền tin \(u_i\) và \(v_i\) \((1 \leq u_i \neq v_i \leq n)\), liên kết này có giới hạn băng thông là \(w_i\) \((1 \leq w_i \leq 10^9)\). Hệ thống được thiết kế như một đồ thị cây, nghĩa là giữa bất kỳ hai trạm bất kỳ luôn tồn tại đúng một tuyến truyền dữ liệu duy nhất.

Khi truyền dữ liệu giữa hai trạm bất kỳ, giới hạn của đường truyền được xác định là giá trị nhỏ nhất trong tất cả các giới hạn băng thông trên đường đi.

Một mạng con Binance được định nghĩa là một nhóm các trạm mạng trên hệ thống. Mạng con, nói một cách cụ thể hơn, là mạng bao gồm các trạm truyền tin \(k_1, k_2, k_3, ..., k_m\) (với \(m\) là số lượng trạm truyền tin trong mạng). Để xác thực dữ liệu một cách mạnh mẽ nhất, các nhà khoa học muốn tìm ra cặp trạm \((k_i, k_j)\) trong mạng con sao cho đường truyền giữa chúng có giới hạn là lớn nhất trong tất cả các cặp --- gọi đó là đường kính của mạng Binance.

Để đánh giá được chất lượng của toàn bộ \(n\) trạm truyền tin trong mạng, ban đánh giá của mạng con này sẽ đưa ra \(Q\) phép thử, mỗi phép thử thứ \(i\) gồm \(m\) trạm truyền tin \(k_1, k_2, ..., k_m\). Với mỗi phép thử, bạn hãy tính toán đường kính của mạng con được cho.

Nhiệm vụ của bạn: Với mỗi mạng con Binance, hãy giúp họ xác định đường kính của mạng con này.

Input

• Dòng đầu chứa số nguyên \(n\) --- số trạm mạng \((1 \leq n \leq 10^5)\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(u_i, v_i, w_i\) --- mô tả kết nối trực tiếp giữa trạm \(u_i\) và \(v_i\) với giới hạn truyền tải \(w_i\) \((1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^9)\).
• Dòng tiếp theo chứa số nguyên \(Q\) --- số phép thử cần xử lí \((1 \leq Q \leq 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng có dạng \(m\ k_1\ k_2\ \dots\ k_m\) --- mô tả một mạng con gồm \(m\) trạm \((2 \leq m \leq n)\).

Output

Với mỗi truy vấn, in ra một dòng duy nhất là đường kính xác thực của mạng Binance tương ứng.

Example

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

4
1
5
3

Scoring

Gọi \(T\) là tổng số lượng đỉnh trong tất cả \(Q\) phép thử.

• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 100, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 10^5, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 100\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm \(n, T, Q \leq 10^5\), mỗi trạm truyền tin chỉ liên kết tối đa với \(2\) trạm truyền tin khác.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Trong thế giới phép thuật, một người gác cổng trẻ tuổi tên là Minh được giao nhiệm vụ bảo vệ \(n\) cánh cổng thần bí, được đánh số từ \(1\) đến \(n\). Tại mỗi cánh cổng thứ \(i\) có một chiếc hộp chứa kho báu và một lò xo dịch chuyển.

• Lò xo có độ đàn hồi có thể điều chỉnh trong một khoảng \([L_i, H_i]\).
• Bốn loại báu vật được cất giữ, đánh số từ \(1\) đến \(4\), mỗi loại có một giá trị nhất định.

Để mở hộp, Minh cần dùng một chìa khóa ma thuật là một chuỗi 4 bit. Mỗi bit 1 tương ứng với việc lấy một loại báu vật. Ví dụ, với chìa khóa \(0110\), Minh sẽ nhận được báu vật loại \(2\) và \(3\).

Sau khi lấy kho báu, Minh sẽ dùng lò xo để dịch chuyển đến một cánh cổng khác. Nếu điều chỉnh độ đàn hồi của lò xo là \(k\) (\(k \in [L_i, H_i]\)), anh ta sẽ dịch chuyển đến cổng \(i+k\). Nếu \(i+k > n\), anh ta sẽ dịch chuyển ra khỏi khu vực bảo vệ.

Có một số quy tắc đặc biệt mà Minh phải tuân thủ:

• Chìa khóa không được có hai bit \(1\) liền kề.
• Hai chìa khóa sử dụng liên tiếp không được có bit \(1\) ở cùng một vị trí. Ví dụ, nếu vừa dùng chìa \(0010\) thì chìa \(1010\) ở bước tiếp theo sẽ không hợp lệ.
• Minh phải lấy ít nhất một loại báu vật.
• Hành trình của Minh chỉ kết thúc khi anh ta dịch chuyển ra khỏi khu vực bảo vệ.

Minh bắt đầu từ cánh cổng \(1\). Anh ta muốn đi qua các cổng và thu thập báu vật một cách hợp lệ để đạt được tổng giá trị lớn nhất có thể.

Yêu cầu:
Hãy tính tổng giá trị báu vật lớn nhất mà Minh có thể thu thập.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(n \le 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(6\) số nguyên: \(L_i, H_i\) và giá trị của \(4\) món báu vật ở cổng thứ \(i\) \((0 < L_i \le H_i \le 10^9)\). Giá trị của các món báu vật có giá trị tuyệt đối nhỏ hơn hoặc bằng \(10^9\).

Output

• Một số nguyên duy nhất là giá trị tối đa có thể thu thập.

Example

6
1 1 3 2 -4 5
1 2 2 -3 1 3
2 2 1 1 -1 -1
1 3 -10 10 30 33
1 1 2 3 -5 4
1 100 2 2 2 2

59

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 10\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(L_i = H_i\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Chúng ta hình dung đường bờ biển như một dãy số \(h_1, h_2, \ldots, h_n\), trong đó \(h_i\) biểu thị độ cao của địa hình tại điểm thứ \(i\). Có \(q\) truy vấn, mỗi truy vấn được mô tả như sau: Có bao nhiêu hòn đảo sẽ xuất hiện khi chỉ xét các điểm từ \(l_i\) đến \(r_i\) nếu mực nước biển dâng lên \(x_i\) mét?

Một hòn đảo được định nghĩa là một đoạn liên tiếp dài nhất (maximal interval) mà mỗi phần tử \(h_i\) trong đoạn đó đều lớn hơn mức nước biển. Một đoạn liên tiếp là dài nhất nếu không thể mở rộng thêm về bên trái hoặc bên phải mà vẫn thỏa điều kiện.

\begincenter

\smallHình minh họa khi xét các điểm từ \(3\) đến \(6\) và mực nước \(x=2\).

\smallVới ví dụ này thì số hòn đảo là \(2\) (\([3,4]\) và \([6,6]\)).

\endcenter

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- độ dài của dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\) (\(0 \le h_i \le 10^9\)) --- độ cao địa hình.
• Mỗi dòng trong số \(q\) dòng tiếp theo chứa ba số nguyên \(l_i, r_i, x_i\) (\(1 \le l_i \le r_i \le n\), \(0 \le x_i \le 10^9\)) mô tả một truy vấn.

Output

• Ghi ra \(q\) dòng, mỗi dòng chứa số lượng đảo tương ứng với truy vấn thứ \(i\). Các truy vấn là độc lập nhau.

Example

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

2
1
0

10 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 2

2
4
3

Scoring

• Subtask 1 (20 điểm): \(n, q \le 2000\).
• Subtask 2 (20 điểm): \(l_i = 1\), \(r_i = n\) với mọi \(i = 1, 2, \ldots, q\).
• Subtask 3 (10 điểm): Tồn tại một số nguyên \(p\) (\(1 \le p \le n\)) sao cho:
  \(h_1 \ge h_2 \ge \cdots \ge h_p \le h_{p+1} \le \cdots \le h_n.\)
• Subtask 4 (50 điểm): Không có ràng buộc bổ sung.