Ở một thế giới song song giả tưởng không có thật, NQStudio vừa cho ra mắt tựa game Tê Ép Tê (TET) – một trò chơi đấu trí chiến thuật đỉnh cao, đòi hỏi tư duy nhanh nhạy, phụ thuộc vào nhân phẩm và không tài xỉu trá hình!

Trong thế giới này, để chuẩn bị cho trận chiến, người chơi phải mua và ghép các quân cờ lại với nhau. Cờ thủ Chancc đã chuẩn bị sẵn một bộ sưu tập vô hạn các quân cờ có giá trị tuân theo dãy Fibonacci: ~1, 1, 2, 3, 5, 8, 13, 21, \dots~ (mỗi loại quân cờ có thể mua với số lượng tùy ý).

Định nghĩa dãy Fibonacci: Là dãy số bắt đầu bằng ~F_1 = 1, F_2 = 1~, các số đứng sau bằng tổng của hai số đứng liền trước: ~F_k = F_{k-1} + F_{k-2}~ với ~k \ge 3~.

Bây giờ, Chancc cần ghép thành công ~n~ quân cờ mục tiêu, quân cờ thứ ~i~ có giá trị bằng ~x_i~ vàng. Để ghép được quân cờ giá trị ~x_i~, Chancc cần chọn ra ~m_i~ quân cờ từ bộ sưu tập Fibonacci sao cho tổng giá trị của ~m_i~ quân cờ này đúng bằng ~x_i~. Hãy giúp Chancc tìm cách chọn mua số lượng quân cờ ít nhất có thể cho mỗi quân cờ mục tiêu!

Đầu vào

• Dòng thứ nhất chứa số nguyên ~n~ - số lượng quân cờ mục tiêu.
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1, x_2, \dots, x_n~ - giá trị của từng quân cờ mục tiêu.

Đầu ra

In ra ~n~ dòng. Với dòng thứ ~i~ (tương ứng với quân cờ mục tiêu có giá trị ~x_i~):

• Số đầu tiên là ~m_i~ - số lượng quân cờ Fibonacci mà bạn chọn mua.
• ~m_i~ số tiếp theo ~a_1, a_2, \dots, a_{m_i}~ là giá trị của từng quân cờ chọn mua (mỗi ~a_j~ phải là một số Fibonacci). Bài tập chấp nhận nhiều lời giải, xem thêm ở bên dưới.

Giới hạn

• 50% số test: ~n \le 10~ và ~x_i \le 100~.
• 30% số test: ~n \le 10^5~ và ~x_i \le 10^5~.
• 20% số test: ~n \le 10^5~ và ~x_i \le 10^{18}~.

Ví dụ

Đầu vào

3
21 4 10

Đầu ra (Tối ưu)

1 21
2 3 1
2 5 5

Giải thích

• Quân cờ 1 (~x_1 = 21~): Chọn ~m_1 = 1~ quân cờ có giá trị là 21 (~21 = 21~).
• Quân cờ 2 (~x_2 = 4~): Chọn ~m_2 = 2~ quân cờ có giá trị là 3 và 1 (~3 + 1 = 4~).
• Quân cờ 3 (~x_3 = 10~): Chọn ~m_3 = 2~ quân cờ có giá trị là 5 và 5 (~5 + 5 = 10~).

Một đầu ra chấp nhận được khác (Chưa tối ưu)

1 21
4 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1

• Lưu ý: Đầu ra này vẫn hợp lệ vì các giá trị bán ra đều là số Fibonacci và có tổng đúng bằng giá trị mục tiêu, tuy nhiên số lượng quân cờ ~m_i~ chưa tối ưu nên sẽ được tính điểm theo quy tắc dưới đây.

Cách tính điểm (Scoring)

Gọi ~ans_i~ là số lượng quân cờ tối thiểu trong đáp án chuẩn của tác giả cho quân cờ thứ ~i~.

Với mỗi quân cờ mục tiêu thứ ~i~, điểm số ~S_i~ cho quân cờ đó được tính như sau:

1. Không hợp lệ: Nếu ~\sum_{j=1}^{m_i} a_j \neq x_i~ hoặc tồn tại ~a_j~ không phải là số Fibonacci, bạn nhận ~0~ điểm (~S_i = 0~).
2. Tối ưu bằng hoặc tốt hơn tác giả: Nếu tổng hợp lệ và ~m_i \le ans_i~, bạn nhận tối đa ~1~ điểm (~S_i = 1~).
3. Chưa tối ưu: Nếu tổng hợp lệ nhưng ~m_i > ans_i~, điểm số thu được cho câu đó là ~S_i = \sqrt{\dfrac{ans_i}{m_i}}~.

Điểm tổng kết của bài làm = ~\left(\frac{\sum_{i=1}^n S_i}{n}\right) \times 100\%~

Ví dụ tính điểm:

Xét với Ví dụ trên (~n = 3~, đáp án tối ưu của tác giả có ~ans_1 = 1, ans_2 = 2, ans_3 = 2~):

• Nếu nộp "Đầu ra (Tối ưu)":

  • ~S_1 = 1, S_2 = 1, S_3 = 1~.
  • Điểm tổng kết: ~\frac{1 + 1 + 1}{3} \times 100\% = 100\%~ số điểm.

• Nếu nộp "Đầu ra chấp nhận được khác":

  • Quân cờ 1 (~m_1 = 1 \le ans_1~): ~S_1 = 1~ điểm.
  • Quân cờ 2 (~m_2 = 4 > ans_2~): ~S_2 = \sqrt{\frac{ans_2}{m_2}} = \sqrt{\frac{2}{4}} \approx 0.71~ điểm.
  • Quân cờ 3 (~m_3 = 10 > ans_3~): ~S_3 = \sqrt{\frac{ans_3}{m_3}} = \sqrt{\frac{2}{10}} \approx 0.45~ điểm.
  • Điểm tổng kết: ~\frac{1 + 0.71 + 0.45}{3} \times 100\% \approx 72\%~ số điểm.

Cho một số nguyên dương ~n~. Hãy tìm hai số nguyên ~p~ và ~x~ sao cho tích của ~p~ và ~x~ đúng bằng ~n~ (~p \times x = n~).

Đầu vào

• Dòng duy nhất chứa một số nguyên dương ~n~.

Đầu ra

• In ra hai số nguyên ~p~ và ~x~ trên cùng một dòng, cách nhau bởi một khoảng trắng.
• Bài tập chấp nhận nhiều lời giải (nếu có nhiều cặp ~(p, x)~ thỏa mãn ~p \times x = n~, bạn chỉ cần in ra một cặp bất kỳ).

Giới hạn

• 50% số test: ~n \le 10^{12}~.
• 50% số test còn lại: ~n \le 10^{18}~.

Ví dụ

Đầu vào

6

Đầu ra

2 3

Giải thích

• Hai số ~p = 2~ và ~x = 3~ thỏa mãn ~2 \times 3 = 6~.

V bị lạc trong một mê cung. Ở mỗi ngã rẽ, trước mặt V luôn có ba lối: bên trái, đi thẳng và bên phải. Loay hoay mãi chưa tìm được đường ra, V tình cờ gặp L.

L biết rõ mê cung này. Theo lời L, từ chỗ hai người đang đứng, V chỉ cần liên tiếp chọn lối bên trái x lần, sau đó liên tiếp đi thẳng y lần, rồi liên tiếp chọn lối bên phải z lần là sẽ đến được lối ra. Ba số x,y,z đều là số nguyên không âm.

Thấy V mừng rỡ, L lại nảy ý định trêu chọc. L giấu ba con số ấy và chỉ cho V hỏi đúng năm câu hỏi. Mỗi lần, V được chọn ba số nguyên a,b,c, với ~0 \le a,b,c \le 100~, để hỏi giá trị của:

$$ ax+by+cz $$

Chẳng hạn, chọn ~a=2,b=0,c=1~ nghĩa là V muốn biết hai lần số ngã rẽ cần chọn lối bên trái cộng với số ngã rẽ cần chọn lối bên phải bằng bao nhiêu.

Vốn biết L rất ranh mãnh, V hiểu rằng không thể tin ngay mọi câu trả lời. Tuy vậy, V cũng biết L chỉ định trêu mình đôi chút: trong cả năm câu trả lời, L sẽ nói dối nhiều nhất một câu. Những câu còn lại đều cho đúng giá trị mà V hỏi.

V không muốn tiếp tục lang thang trong mê cung nữa. Hãy giúp V đặt năm câu hỏi và xác định chính xác x,y,z để tìm đường ra.

Phương thức tương tác

Đây là một bài toán tương tác. Chương trình của bạn sẽ trao đổi dữ liệu với chương trình chấm, đóng vai L, thông qua đầu vào chuẩn và đầu ra chuẩn. Ba giá trị x,y,z được giữ cố định trong suốt quá trình tương tác.

Không có dữ liệu đầu vào ban đầu. Chương trình của bạn phải gửi câu hỏi trước khi đọc phản hồi.

Quá trình tương tác gồm đúng 5 lượt, mỗi lượt thực hiện như sau:

1. In ra một dòng chứa ba số nguyên a,b,c cách nhau bởi dấu cách, thỏa mãn ~0 \le a,b,c \le 100~.
2. Xuống dòng và đẩy bộ đệm đầu ra (flush).
3. Đọc một số nguyên r từ đầu vào chuẩn, là câu trả lời của chương trình chấm. Mọi phản hồi đều thỏa mãn ~0\le r\le10^5~.

Trong ít nhất 4 lượt, phản hồi thỏa mãn ~r=ax+by+cz~. Trong nhiều nhất 1 lượt, phản hồi có thể khác giá trị này. Cũng có thể cả 5 câu trả lời đều đúng.

Sau khi nhận đủ 5 phản hồi, in ra một dòng chứa ba số nguyên không âm x,y,z mà bạn xác định được, cách nhau bởi dấu cách. Sau đó xuống dòng, flush và kết thúc chương trình.

Ví dụ tương tác

Các hàng dưới đây được trình bày theo thứ tự thời gian. Dấu — biểu thị bên đó không gửi dữ liệu ở bước tương ứng và không phải là một phần của dữ liệu.

Trong ví dụ này, ba giá trị bí mật là ~x=y=z=4~. Câu trả lời thứ hai là nói dối vì ~x+y+z=12~, không phải ~13~. Bốn câu trả lời còn lại đều là nói thật. Dòng cuối cùng 4 4 4 là kết quả mà chương trình của bạn đưa ra, chương trình chấm không gửi thêm phản hồi.

Hướng dẫn nhập/xuất cho bài tương tác

Sau mỗi truy vấn, chương trình phải flush đầu ra trước khi đọc phản hồi. Nếu không, truy vấn có thể vẫn nằm trong bộ đệm và chưa được gửi tới chương trình chấm, khiến chương trình phải chờ và vượt quá giới hạn thời gian.

Với C++:

cout << a << ' ' << b << ' ' << c << endl;
// endl vừa xuống dòng, vừa flush đầu ra.

long long r;
cin >> r;

Nếu sử dụng '\n' thay cho endl, cần gọi cout.flush() trước khi đọc phản hồi.

Với Python:

print(a, b, c, flush=True)
r = int(input())

Những đoạn mã trên chỉ minh họa thao tác gửi một truy vấn và nhận một phản hồi.

Chương trình phải gửi đúng 5 truy vấn rồi mới đưa ra kết quả. Không in lời nhắc nhập dữ liệu, lời giải thích hoặc thông tin gỡ lỗi ra đầu ra chuẩn.

Lưu ý: Ví dụ tương tác không phải một tệp đầu vào thông thường để sao chép nguyên khối vào chương trình. Khi chấm, mỗi phản hồi chỉ được gửi sau khi chương trình của bạn đưa ra truy vấn tương ứng.

Đêm Halloween sắp đến, Quốc Vương Vịt quyết định tổ chức Kỳ thi Nông Dân Tài Ba để chọn ra người trồng bí ngô giỏi nhất vương quốc. Vịt Vàng, chú vịt vui tính nhất vùng đầm sen, hăng hái ghi danh tham dự.

Đề thi như sau. Vịt Vàng được giao một luống đất dài, trên đó chú trồng n gốc bí ngô thành một hàng, đánh số từ 1 đến n theo thứ tự từ trái sang phải. Quả bí ngô thứ i có điểm ma thuật là ~a_i~. Bí ngô cười tươi có ~a_i~ dương, mang lại may mắn và niềm vui. Nhưng cũng có những quả bí ngô bị nguyền, có ~a_i~ âm, vì chúng mang lại xui xẻo và tai ương cho mọi người.

Để thử tài các thí sinh, Quốc Vương ban cho mỗi người một cây gậy phép và một chiếc giỏ thu hoạch. Vịt Vàng phải thực hiện hai bước, theo đúng thứ tự:

• Bước 1 (Phép đảo ngược): Chọn hai vị trí l, r (~1 \le l \le r \le n~). Vịt Vàng vung gậy phép để đảo ngược thứ tự các quả bí ngô trong đoạn từ vị trí l đến vị trí r.
• Bước 2 (Thu hoạch): Chọn một số nguyên k (~0 \le k \le n~). Vịt Vàng chỉ hái k quả bí ngô đầu tiên tính từ bên trái (sau khi đã đảo) bỏ vào giỏ. Những quả còn lại bị bỏ lại trên luống.

Điểm số của Vịt Vàng bằng tổng điểm ma thuật của các quả bí ngô trong giỏ. Nếu Vịt Vàng chọn k = 0, giỏ trống và điểm số bằng 0.

Hãy giúp Vịt Vàng chọn l, r, k sao cho điểm số đạt được là lớn nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (~1 \le t \le 10^4~) — số lượng bộ test.

Với mỗi bộ test:

• Dòng đầu tiên chứa số nguyên n (~2 \le n \le 2 \cdot 10^5~).
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Tổng n trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất — điểm số lớn nhất mà Vịt Vàng có thể đạt được.

Ví dụ

Input

4
6
4 -5 3 -2 6 -8
3
-3 -1 -2
7
2 -1 -4 7 -3 8 -6
2
-4 10

Output

11
0
14
10

Giải thích

• Test 1: Vịt Vàng đảo đoạn ~[2, 5]~, luống bí ngô thành ~4, 6, -2, 3, -5, -8~. Chú hái ~k = 4~ quả đầu tiên, được ~4 + 6 - 2 + 3 = 11~.
• Test 2: Toàn bộ bí ngô đều bị nguyền, nên tốt nhất là không hái quả nào ~(k = 0)~, điểm số bằng 0.
• Test 3: Vịt Vàng đảo đoạn ~[2, 6]~, luống bí ngô thành ~2, 8, -3, 7, -4, -1, -6~. Chú hái ~k = 4~ quả đầu tiên, được ~2 + 8 - 3 + 7 = 14~.
• Test 4: Vịt Vàng đảo đoạn ~[1, 2]~, luống bí ngô thành ~10, -4~. Chú hái ~k = 1~ quả đầu tiên, được ~10~.

Cho dãy ~a~ gồm ~n~ số nguyên.

Bạn phải trả lời ~q~ truy vấn. Mỗi truy vấn cho hai số nguyên ~b, c~, bạn cần tìm số cặp ~(i, j)~ thỏa mãn:

• ~1 \le i < j \le n~.
• ~a_i + a_j = b~.
• ~a_i \times a_j = c~.

Đầu vào

• Dòng thứ nhất chứa một số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le |a_i| \le 10^9~).
• Dòng thứ ba chứa một số nguyên dương ~q~ (~1 \le q \le 2 \times 10^5~).
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~b, c~ mô tả một truy vấn (~1 \le |b| \le 2 \times 10^9~; ~1 \le |c| \le 10^{18}~).

Đầu ra

Với mỗi truy vấn theo đúng thứ tự trong đầu vào, in ra một dòng một số nguyên duy nhất là số cặp ~(i, j)~ thỏa mãn các điều kiện trên.

Giới hạn

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10^3~, ~q = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~|a_i| \le 10^6~, ~|c| \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~|c| \le 10^9~.
• Subtask ~4~ (~20\%~ số điểm): Các phần tử ~a_i~ phân biệt từng đôi một.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

3
1 3 2
1
3 2

Đầu ra

1

Giữa thảo nguyên rộng lớn, một người lữ hành đang trên đường tìm đến ngôi làng nằm ở phía bên kia vùng đất. Tuy nhiên, thảo nguyên không hoàn toàn bằng phẳng mà trải dài với những ngọn đồi, thung lũng và các vùng đất có độ cao khác nhau.

Để lên kế hoạch cho chuyến đi, người lữ hành sử dụng một tấm bản đồ được chia thành ~N * N~ ô vuông. Mỗi ô mang một giá trị nguyên dương biểu thị độ cao của vùng đất tương ứng.

Người lữ hành bắt đầu từ ô ở góc trên bên trái và cần đến ô ở góc dưới bên phải của bản đồ. Tại mỗi bước, người đó có thể di chuyển sang một trong bốn ô kề cạnh: trên, dưới, trái hoặc phải.

Do địa hình gồ ghề, những đoạn đường có độ cao thay đổi đột ngột sẽ rất khó vượt qua. Vì vậy, người lữ hành muốn tìm một con đường tránh được những đoạn dốc quá lớn.

Hãy giúp người lữ hành tìm một con đường sao cho độ chênh lệch độ cao lớn nhất giữa hai ô liên tiếp trên đường đi là nhỏ nhất có thể.

Đầu vào

Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 500)~ là kích thước của bản đồ.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~N~ số nguyên ~A[i][1], A[i][2], \ldots, A[i][N]~, trong đó ~A[i][j]~ là độ cao của ô ở hàng ~i~, cột ~j~ ~(1 \le A[i][j] \le 10^6)~.

Đầu ra

In ra một số nguyên duy nhất là độ chênh lệch độ cao lớn nhất giữa hai ô liên tiếp trên con đường tối ưu.

Subtask

Ví dụ

Đầu vào

4
3 5 7 7
2 4 4 7
3 3 5 4
9 5 8 5

Đầu ra

1

Giải thích

Trong buổi yến tiệc do thầy NamDVH tổ chức, có ~n~ món ăn được xếp thành một hàng. Mỗi món thứ ~i~ có độ thơm là ~a_i~ và và độ bắt mắt là ~b_i~.

Thầy có thể chọn một hoặc nhiều đoạn món ăn liên tiếp, sao cho các đoạn đôi một không giao nhau. Độ ngon miệng của một đoạn ~[l,r]~ các món ăn liên tiêp được được tính theo công thức:

~|b_l-a_r|+|b_r-a_l|~.

Thầy muốn các bạn sinh viên của thầy tìm ra các đoạn sao cho tổng số món nằm trong các đoạn được chọn bằng đúng ~k~. Nhưng không chỉ vậy, thầy còn muốn đoạn đó có tổng độ ngon miệng là lớn nhất có thể. Các bạn sinh viên hãy tìm giúp thầy NamDVH!

Đầu vào

• Dòng đầu chứa số nguyên dương ~t~ (~1 \le t \le 1000~) — số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Một dòng chứa hai số nguyên ~n,k~ (~1 \le k \le n \le 3000~).
  • Một dòng chứa ~n~ số nguyên ~a_1,a_2,\ldots,a_n~.
  • Một dòng chứa ~n~ số nguyên ~b_1,b_2,\ldots,b_n~.

Đầu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — tổng điểm lớn nhất có thể đạt được.

Giới hạn

• ~-10^9 \le a_i,b_i \le 10^9~.
• Tổng ~n~ trên tất cả các bộ dữ liệu không vượt quá ~3000~.

Giới hạn theo subtask

• Subtask ~1~ (~10\%~ số điểm): ~k=1~.
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~.
• Subtask ~3~ (~60\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

1
4 2
1 4 2 5
5 2 4 1

Đầu ra

16

Giải thích

Có thể chọn hai đoạn ~[1,1]~ và ~[4,4]~. Mỗi đoạn có ~8~ điểm, nên tổng điểm là ~16~.

Zero-G là môi trường không trọng lực mà một tàu chở hàng liên hành tinh đang trôi dạt. Tàu mang theo ~n~ thùng hàng xếp thành một hàng dọc, đánh số thứ tự từ ~1~ đến ~n~. Thùng thứ ~i~ mang mã loại hàng là một số nguyên ~a_i~ (mã chỉ dùng để phân biệt các loại hàng).

Để đảm bảo chuyến bay diễn ra an toàn, mỗi loại hàng trên tàu phải có số lượng thùng nằm trong một mức nhất định: quá ít thì không đủ phục vụ hành trình, quá nhiều thì làm mất cân bằng tải trọng trong môi trường không trọng lực. Vì vậy, cơ quan kiểm định đưa ra hai ngưỡng ~A~ và ~B~ (~A \le B~). Khi kiểm tra một đoạn thùng hàng liên tiếp:

• Với mỗi loại hàng ~x~, gọi ~c_x~ là số lượng thùng loại x xuất hiện trong đoạn đó.
• Loại hàng ~x~ được gọi là an toàn nếu số lượng thùng của nó thỏa mãn: ~A \le c_x \le B~

Lưu ý: Điều kiện kiểm định chỉ xét trên số lượng thùng ~c_x~, không phụ thuộc vào giá trị mã ~x~. Loại hàng không xuất hiện trong đoạn có ~c_x = 0~, do ~A \ge 1~ nên không được tính là an toàn.

Có ~q~ đợt kiểm định. Mỗi đợt yêu cầu kiểm tra một đoạn từ thùng ~l~ đến thùng ~r~. Hãy đếm số loại hàng an toàn trong từng đợt kiểm định.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên ~n, q, A, B~ (~1 \le n, q \le 10^6~; ~1 \le A \le B \le n~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) — mã loại hàng của các thùng.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ (~1 \le l \le r \le n~) mô tả một đoạn cần kiểm định.

Dữ liệu ra

In ra ~q~ dòng, dòng thứ ~j~ là số loại hàng an toàn của đợt kiểm định thứ ~j~.

Ví dụ

Input

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

Output

1
2
2
2
1

Giải thích ví dụ (đợt 1 với ~l = 1, r = 10~ và ~A = 2, B = 3~):

Đoạn ~[1, 10]~ chứa toàn bộ các thùng: 1 2 1 3 2 1 2 2 3 1.

Chỉ có loại hàng 3 an toàn nên kết quả là 1.

Subtask

"Ngày xửa ngày xưa, có một Vùng đất Kỳ diệu được tạo ra bằng phép thuật của _minhduc..."

Tại Vùng đất Kỳ diệu — nơi tạo ra những cốc nước ép ngon nhất thế giới, có một mạng lưới gồm ~n~ thành phố chuyên dùng để pha chế nước ép. Các thành phố được đánh số từ ~1~ đến ~n~ và được kết nối với nhau bởi ~n - 1~ con đường hai chiều, đảm bảo luôn có thể đi từ bất kỳ thành phố nào đến thành phố khác.

Mỗi thành phố độc quyền sản xuất một loại nguyên liệu nước ép. Cụ thể, thành phố thứ ~i~ cung cấp loại nguyên liệu có độ ngon là ~d_i~, giá bán mỗi lít là ~p_i~ và trữ lượng tối đa là ~l_i~ lít.

Trong dịp lễ hội, có ~m~ đứa trẻ lần lượt đến tham quan vùng đất này. Các đứa trẻ được đánh số từ ~1~ đến ~m~. Đứa trẻ thứ ~j~ thực hiện một chuyến du lịch đi từ thành phố ~u_j~ đến thành phố ~v_j~. Trong quá trình di chuyển, đứa trẻ này có một yêu cầu pha chế nước ép như sau:

• Chỉ được phép mua nguyên liệu tại các thành phố nằm trên đường đi ngắn nhất từ ~u_j~ đến ~v_j~ (bao gồm cả ~u_j~ và ~v_j~).
• Cần mua tổng cộng ít nhất ~L_j~ lít nguyên liệu để pha thành một ly nước ép hỗn hợp.
• Tổng số tiền chi trả cho lượng nguyên liệu được mua không được vượt quá ~g_j~.

Độ ngon của một ly nước ép hỗn hợp được định nghĩa là giá trị nhỏ nhất trong số các độ ngon của những nguyên liệu được chọn để pha chế.

Sau khi một đứa trẻ nhận được nước ép, nó hài lòng và rời khỏi Vùng đất Kỳ diệu ngay lập tức. Khi đó, các thành phố sẽ bước vào trạng thái nạp năng lượng - các thành phố sẽ làm đầy trữ lượng nước ép nếu đã bị sử dụng bởi đứa trẻ vừa thăm quan để chuẩn bị tiếp đón đứa trẻ tiếp theo. Khi đứa trẻ kế tiếp bước vào Vùng đất Kỳ diệu, mọi thành phố đều ở trạng thái đã đầy đủ trữ lượng nước ép tối đa có thể chứa. Nói cách khác, mọi yêu cầu của ~m~ đứa trẻ sẽ độc lập với nhau; trước mỗi yêu cầu, thành phố ~i~ luôn có đủ ~l_i~ lít nguyên liệu, nhằm đảm bảo sự công bằng và giữ lại niềm vui trọn vẹn cho mọi đứa trẻ tham quan Vùng đất Kỳ diệu này.

Yêu cầu: Với mỗi đứa trẻ, hãy xác định cách chọn mua nguyên liệu sao cho thỏa mãn tất cả các điều kiện trên, đồng thời độ ngon của ly nước ép hỗn hợp đạt giá trị lớn nhất có thể. Nếu không có cách nào mua đủ nguyên liệu hoặc chi phí vượt quá giới hạn, hãy trả về kết quả là ~-1~.

Đầu vào

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 10^5~) — lần lượt là số thành phố và số đứa trẻ.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~d_i, p_i, l_i~ (~1 \le d_i, p_i, l_i \le 10^5~) — lần lượt mô tả độ ngon, giá bán mỗi lít và trữ lượng tối đa của nguyên liệu tại thành phố ~i~.
• Trong ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ (~1 \le x, y \le n~) — mô tả một con đường hai chiều nối thành phố ~x~ với thành phố ~y~.
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên ~u_j, v_j, g_j, L_j~ (~1 \le u_j, v_j \le n~; ~1 \le g_j, L_j \le 10^{18}~) — mô tả thành phố xuất phát, thành phố kết thúc, ngân sách và lượng nguyên liệu tối thiểu cần mua của đứa trẻ thứ ~j~.

Đầu ra

Gồm ~m~ dòng, dòng thứ ~j~ in ra một số nguyên duy nhất là độ ngon lớn nhất của ly nước ép hỗn hợp mà đứa trẻ thứ ~j~ có thể nhận được. Nếu không thể đáp ứng yêu cầu, in ra ~-1~.

Giới hạn

• Subtask ~1~ (~7.5\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~7.5\%~ số điểm): ~u_j = v_j~ với mọi ~1 \le j \le m~.
• Subtask ~3~ (~10\%~ số điểm): Cấu trúc mạng lưới là một cây nhị phân hoàn hảo.
• Subtask ~4~ (~15\%~ số điểm): ~p_i = 1~ với mọi ~1 \le i \le n~.
• Subtask ~5~ (~15\%~ số điểm): ~l_i = 1~ với mọi ~1 \le i \le n~.
• Subtask ~6~ (~10\%~ số điểm): Thành phố ~i~ liền kề với thành phố ~i + 1~ với mọi ~1 \le i < n~.
• Subtask ~7~ (~10\%~ số điểm): Mỗi thành phố liền kề với tối đa ~2~ thành phố khác.
• Subtask ~8~ (~25\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

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

Đầu ra

3
2

Giải thích

Cấu trúc mạng lưới trong ví dụ là một đường thẳng: thành phố ~1~ nối với thành phố ~2~, thành phố ~2~ nối với thành phố ~3~. Cả hai đứa trẻ đều di chuyển từ thành phố ~1~ đến thành phố ~3~, nên có thể mua nguyên liệu tại cả ba thành phố.

• Với đứa trẻ thứ nhất, ngân sách là ~6~ và cần mua ít nhất ~3~ lít. Để ly nước ép có độ ngon ~3~, chỉ cần mua ~3~ lít nguyên liệu tại thành phố ~3~, với tổng chi phí là ~3 \times 2 = 6~. Do đó, kết quả là ~3~.
• Với đứa trẻ thứ hai, ngân sách là ~5~ và cần mua ít nhất ~3~ lít. Để đạt độ ngon ~3~, phải mua toàn bộ nguyên liệu tại thành phố ~3~, tốn ít nhất ~6~, vượt quá ngân sách. Tuy nhiên, có thể mua ~3~ lít nguyên liệu tại thành phố ~2~ với tổng chi phí là ~3 \times 1 = 3~, thu được ly nước ép có độ ngon ~2~. Do đó, kết quả là ~2~.

Thầy Tichpx luôn thích biến những tiết học toán thành các thử thách bất ngờ. Hôm nay, thầy mang đến lớp một chiếc bảng số đặc biệt: thay vì viết phấn, cả lớp phải điều khiển con số xuất hiện trên bảng.

Ban đầu, tại thời điểm 0, bảng hiển thị số 0. Trong mỗi đơn vị thời gian, số trên bảng chỉ có thể tăng thêm 1, giảm đi 1, hoặc giữ nguyên.

Thầy chuẩn bị n câu đố. Câu đố thứ i xuất hiện đúng tại thời điểm t_i, yêu cầu bảng hiển thị số x_i và mang lại a_i điểm nếu hoàn thành. Một câu đố chỉ được tính điểm khi bảng hiển thị đúng x_i tại thời điểm t_i; sau thời điểm đó, cơ hội nhận điểm sẽ biến mất. Việc hoàn thành câu đố không mất thời gian.

Trong lớp thầy Tichpx, Vuz vốn hay trốn học, nhưng lại nuôi một ước mơ không hề nhỏ: giành được học bổng.

Để biến ước mơ ấy thành hiện thực, Vuz quyết tâm chinh phục những câu đố trên chiếc bảng đặc biệt. Thế nhưng, trước hàng loạt lựa chọn, cậu lại phải phân vân: làm thế nào để giành được nhiều điểm nhất?

Đầu vào

• Dòng đầu tiên chứa số nguyên n — số câu đố.
• n dòng tiếp theo, dòng thứ i chứa ba số nguyên t_i x_i a_i — lần lượt là thời điểm xuất hiện, số cần hiển thị và số điểm của câu đố thứ i.

Các câu đố được cho theo thứ tự bất kỳ.

Đầu ra

In ra một số nguyên duy nhất: tổng số điểm lớn nhất có thể đạt được. Nếu không hoàn thành được câu đố nào, in ra 0.

Giới hạn

• 1 ≤ n ≤ 2 × 10^5.
• 1 ≤ t_i ≤ 10^9.
• -10^9 ≤ x_i ≤ 10^9.
• 1 ≤ a_i ≤ 10^9.
• Không có hai câu đố nào có cùng cặp (t_i, x_i).

Kết quả nằm trong phạm vi số nguyên 64-bit có dấu.

Subtask

Ví dụ

Input

4
1 1 3
2 0 4
2 2 10
3 1 5

Output

18

Giải thích

Một cách đạt điểm tối ưu là điều chỉnh bảng lần lượt như sau:

• Thời điểm 0: hiển thị 0.
• Thời điểm 1: hiển thị 1, nhận 3 điểm.
• Thời điểm 2: hiển thị 2, nhận 10 điểm.
• Thời điểm 3: hiển thị 1, nhận 5 điểm.

Mỗi lần chuyển, giá trị thay đổi không quá 1 trong một đơn vị thời gian. Tổng điểm thu được là 3 + 10 + 5 = 18.

Nhân dịp không phải đi dạy trên trường, thầy NamDVH quyết định đi du lịch tại 1 hòn đảo xa xôi hẻo lánh nhằm tránh xa những xô bồ của cuộc sống. Sau 2 ngày 2 đêm lênh đênh trên biển, cuối cùng thầy cũng đã đến nơi. Sau khi đặt chân đến nơi, thầy bắt đầu đi thăm quan hòn đảo, bỗng nhiên thầy phát hiện ra một mảnh đất kì lạ. Mảnh đất được rào dây theo hình chữ nhật, được tách ra thành ~3~ hàng và ~n~ cột. Sau khi quan sát, thầy đi tới mảnh đất này. Sau khi vào, thầy phát hiện ra khi thầy bước chân vào 1 ô thì tài khoản ngân hàng của thầy tự nhiên nhận được 1 số tiền. Hí hửng, thầy đi qua tất cả các ô, thầy phát hiện ra: khi bước vào 1 ô, tài khoản của thầy có thể nhận tiền hoặc tài khoản của thầy có thể bị trừ tiền (số tiền cộng hoặc trừ đi giữa các ô có thể khác nhau). Hơn nữa, thầy nhận thấy các ô ở hàng thứ 2 bị rào chắn không bước vào được, nhưng các ô ở hàng 1 và hàng 3 có thể đi thoải mái.

Đang suy tư, thì thầy nhận được ~q~ tin nhắn, đọc thì thầy nhận ra đó là những lời mời đặc biệt: Lời mời thứ ~i~ cho phép mở các ô ở hàng thứ hai, từ cột ~l_i~ đến cột ~r_i~, nhưng thầy phải quét mã QR và trả ~c_i~ tiền để chấp nhận lời mời đó. Thầy cũng nhận thêm 1 tin nhắn rằng: "Thầy có thể nhận bất kỳ tập lời mời nào. Nếu nhiều lời mời cùng mở một ô, thầy vẫn phải trả phí của tất cả lời mời đã nhận."

Sau khi đọc hết các tin nhắn, thầy nghĩ ra một bài toán để đố các bạn sinh viên sau khi thầy trở về từ chuyến đi: "Nếu thầy NamDVH bắt đầu tại ô ~(1,1)~ và cần đến ô ~(3,n)~. Mỗi bước, thầy chỉ có thể đi sang phải hoặc đi xuống. Tiền của tất cả các ô thầy đi qua, bao gồm ô bắt đầu và ô kết thúc, sẽ được cộng vào tài khoản của thầy. Để đến đến hàng thứ 3, thầy phải nhận 1 số lời mời đặc biệt ở mở một số ô ở hàng thứ 2, tuy nhiên tài khoản của thầy vẫn có thể nhận được tiền tương ứng nếu đi qua các ô ở hàng thứ 2. Thầy muốn tìm số tiền nhất lớn nhất thầy có thể đạt được sau khi đến ô ~(3, n)~"

Đầu vào

• Dòng đầu chứa hai số nguyên dương ~n,q~ (~1 \le n,q \le 5 \cdot 10^5~).
• Ba dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a_{i,1},a_{i,2},\ldots,a_{i,n}~, mô tả số tiền được nhận của một hàng.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i,r_i,c_i~ — mô tả lời mời thứ ~i~.

Đầu ra

In ra một số nguyên duy nhất — điểm tiền lớn nhất thầy NamDVH có thể đạt được.

Giới hạn

• ~-10^9 \le a_{i,j} \le 10^9~.
• ~1 \le l_i \le r_i \le n~.
• ~1 \le c_i \le 10^9~.

Giới hạn theo subtask

• Subtask ~1~ (~10\%~ số điểm): ~q=1~.
• Subtask ~2~ (~20\%~ số điểm): ~l_i=1~ với mọi ~1 \le i \le q~.
• Subtask ~3~ (~25\%~ số điểm): ~n,q \le 50~.
• Subtask ~4~ (~45\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14

Đầu ra

13

Giải thích

Thầy có thể nhận lời mời thứ hai, mở các ô ở hàng thứ hai từ cột ~2~ đến cột ~3~, rồi đi qua các ô ~(1,1)~, ~(1,2)~, ~(1,3)~, ~(2,3)~, ~(3,3)~, ~(3,4)~. Tổng số tiền các ô là ~17~, phí lời mời là ~4~, nên điểm cuối cùng là ~13~.