Cho dãy số nguyên không âm ~a~ = (~a_1,a_2, … , a_n~). Bạn được thực hiện các phép biến đổi, ở mỗi phép biến đổi bạn tùy chọn một dãy các phần tử liên tiếp trong dãy và trừ tất cả các phần tử này đi 1 đơn vị.

Yêu cầu: Dùng số phép biến đổi ít nhất để biến tất cả các phần tử trong dãy trở thành 0.

Input

Dòng 1 chứa số nguyên dương ~n ≤ 10^6~

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (~0 ≤ a_i ≤ 10^6~)

Output

Ghi ra một số nguyên duy nhất là số phép biến đổi cần thực hiện

Test mẫu

Input Sample Output

10
1 2 5 3 4 2 1 5 4 1

Output

10

Giải thích

~1 2 \textbf{5} 3 4 2 1 5 4 1~

~1 2 \textbf{4} 3 4 2 1 5 4 1~

~1 2 3 3 \textbf{4} 2 1 5 4 1~

~1 2 \textbf{3 3 3} 2 1 5 4 1~

~1 \textbf{2 2 2 2 2} 1 5 4 1~

~1 1 1 1 1 1 1 \textbf{5} 4 1~

~1 1 1 1 1 1 1 \textbf{4 4} 1~

~1 1 1 1 1 1 1 \textbf{3 3} 1~

~1 1 1 1 1 1 1 \textbf{2 2} 1~

~\textbf{1 1 1 1 1 1 1 1 1 1}~

~0 0 0 0 0 0 0 0 0 0~

Subtasks

~40\%~ số điểm ứng với các test có ~n ≤ 1000~

~30\%~ số điểm ứng với các test có ~n ≤ 10^5~

~30\%~ số điểm không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề

Con chuột Hamster của giáo sư X bị quá cân và ông bắt nó phải chạy với bánh xe vô cực. Bánh xe là một vòng tròn gồm ~n~ ô đánh số từ 1 tới ~n~. Theo chiều chạy, tiếp theo ô 1 là ô 2, tiếp theo ô 2 là ô 3, … tiếp theo ô ~n~ là ô 1. Trên ô thứ ~i~ có in nhãn là số nguyên ~a_i~ . Ban đầu con chuột đứng ở ô ~n~ và giáo sư X lập trình trước bộ điều khiển bánh xe đọc lần lượt các số nguyên dương ~b_1, b_2, … , b_m~. Khi máy đọc số ~b_i~, màn hình sẽ hiện số 0 và bánh xe bắt đầu quay bắt buộc con chuột phải chạy tới ô kế tiếp trên vòng. Chạy tới ô nào màn hình sẽ cộng thêm nhãn của ô đó vào số đang có… và khi số trên màn hình vừa đủ ~\ge b_i~, bánh xe sẽ dừng cho con chuột nghỉ tại chỗ một lát trước khi bánh xe lặp lại quá trình đó với số ~b_{i+1}~(nếu có)

Yêu cầu: Vốn không thích quá trình tập luyện nhàm chán, con chuột Hamster muốn nhẩm tính khi bộ điều khiển bánh xe đọc vào mỗi số nguyên trong dãy ~b_1, b_2, ..., b_m~ hiện bao nhiêu lần di chuyển từ một ô sang ô kế tiếp

Input

Dòng 1 chứa số nguyên dương ~n~ (~2 \le n \le 10^5~)

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~-10^9 ≤ a_i ≤ 10^9~)

Dòng 3 chứa số nguyên dương ~𝑚 ≤ 10^5~ ~m~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~b_i~ (~1 ≤ b_i ≤ 10^9~)

Các số trên một dòng của input được ghi cách nhau bởi dấu cách. Dữ liệu vào đảm bảo dãy 𝑎 có tổng dương.

Output

Với mỗi số trong dãy ~b_1, b_2, ..., b_m~ theo đúng thứ tự, ghi ra trên một dòng số lần di chuyển từ một ô sang ô kế tiếp mà con chuột phải thực hiện khi bộ điều khiển đọc được số đó.

Test mẫu

Input

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

Output

1
6
12

Giải thích

Ban đầu đứng ở ô nhãn 8 b[1] = 1 : 1 lần di chuyển tới ô nhãn 2 b[2] = 4 : 6 lần di chuyển tới các ô có nhãn -3 4 -5 -1 8 2 b[3] = 10: 12 lần di chuyển tới các ô có nhãn -3 4 -5 -1 8 2 -3 4 -5 -1 8 2

Subtasks

~30\%~ số điểm ứng với các test có ~𝑛, 𝑚 ≤ 1000~ và ~𝑏_𝑖 ≤ 1000~

~30\%~ số điểm ứng với các test có ~𝑛, 𝑚 ≤ 1000~

~40\%~ số điểm ứng với các test không có ràng buộc bổ sung ngoài các ràng buộc ban đầu

Một tập đoàn thuê ~n~ bác lao công dọn dẹp tòa nhà trụ sở để đón tiếp một đối tác lớn. Các bác lao công được đánh số từ 1 tới ~n~. Tùy theo tính chất công việc, bác lao công thứ 𝑖 sẽ làm việc trong khoảng thời gian ~[a_i; b_i]~ và nhận khoản tiền là ~w_i~ ngay khi bắt đầu công việc.

Tập đoàn cho phép một bác lao công ~i~ khi nhận tiền có thể nhận hộ những người khác có thời gian lao động nằm hoàn toàn trong khoảng thời gian lao động bác ~i~. Cụ thể là bác lao công ~i~ có thể nhận hộ tiền cho bác lao công ~j~ nếu:

~[a_i; b_i] ⊇ [a_j; b_j]⟺ a_i \le a_j < b_j≤ \le b_i~

Ví dụ một bác lao công làm việc trong khoảng thời gian [0; 9] có thể nhận hộ tiền cho các bác lao công làm việc trong khoảng thời gian [0; 2];[4; 6] hoặc [7; 9].

Yêu cầu: Với mỗi ~i~ = 1,2, … , 𝑛, hãy tính ~c_i~ là tổng số tiền bác lao công ~i~ sẽ nhận nếu bác ấy tới nhận tiền của mình và nhận hộ tất cả những người khác có thời gian lao động nằm hoàn toàn trong khoảng thời gian lao động của bác ~i~.

Input

Dòng 1 chứa số nguyên dương ~n ≤ 2 ∗ 10^5~

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i, b_i, w_i~ (~0 ≤ a_i < b_i ≤ 10^9; 1 ≤ w_i ≤ 10^9~)

Output

Ghi ra ~n~ số nguyên trên một dòng, số thứ ~i~ là ~c_i~

Test mẫu

Input

8
0 9 1
1 8 2
2 6 3
0 2 4
5 9 5
2 3 6
4 6 7
7 9 8

Output

36 18 16 4 13 6 7 8

Subtasks

~30\%~ số điểm ứng với các test có ~n ≤ 5000~

~30\%~ số điểm ứng với các test có ~𝑛 ≤ 20000~

~40\%~ số điểm ứng với các test không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề

Có ~n~ học sinh được nhận quà từ ~m~ nhà tài trợ. Các học sinh được đánh số từ 1 tới ~n~ và các nhà tài trợ được đánh số từ 1 tới ~m~. Các bạn học sinh đứng quanh một vòng tròn: Bên phải học sinh 1 là học sinh 2, bên phải học sinh 2 là học sinh 3, … bên phải học sinh ~n~ là học sinh 1.

Lần lượt từng nhà tài trợ sẽ trao một hộp quà cho một học sinh làm đại diện, hộp quà có thể chứa một hoặc nhiều món quà. Khi một học sinh nhận được hộp, bạn đó sẽ lấy ra đúng 1 món quà cho mình rồi chuyển hộp ngay cho bạn bên phải và quá trình cứ tiếp tục như vậy cho tới khi trong hộp không còn món quà nào.

Yêu cầu: Sau khi tất cả các nhà tài trợ đã trao quà, cho biết số món quà nhiều nhất một bạn học sinh được nhận và số bạn học sinh cùng nhận nhiều món quà nhất.

Input

Dòng 1 chứa hai số nguyên dương ~n, m~ (~2 ≤ n ≤ 10^9; 1 ≤ m ≤ 10^5~)

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, k~ (~1 ≤ a ≤ 10^9; 1 ≤ k ≤ n~) tương ứng với thông tin: Một nhà tài trợ trao hộp chứa ~a~ món quà cho học sinh thứ ~k~

Output

Ghi ra một dòng gồm hai số nguyên ~p, q~ trong đó ~p~ là số món quà nhiều nhất mà một bạn học sinh được nhận, còn ~q~ là số bạn học sinh cùng nhận nhiều món quà nhất.

Test mẫu

Input

6 3
5 4
20 1
4 5

Output

6 2

Giải thích: http:///ibb.co/1ffGWsZS

Subtasks

~50\%~ số điểm ứng với các test có ~n, m, a ≤ 10^3~

~30\%~ số điểm ứng với các test có ~n, m ≤ 10^5~

~20\%~ số điểm còn lại không có ràng buộc bổ sung

Cho một cây gồm ~n~ đỉnh đánh số từ 1 tới ~n~. Ba con vật nuôi: Chó, mèo và chuột đứng ở ba đỉnh khác nhau. Chó biết rằng mèo đôi lúc hay bắt nạt chuột và khi đó mèo sẽ di chuyển theo các cạnh trên cây tới nơi chuột đứng. Chó muốn ngăn cản mèo bắt chuột bằng cách di chuyển tới một đỉnh nào đó trên đường đi từ vị trí của mèo tới vị trí của chuột, tuy nhiên do quá béo và lười nên chó muốn chọn đỉnh gần nhất để đi tới.

Yêu cầu: Trả lời ~m~ truy vấn, mỗi truy vấn cho bởi ba số nguyên hoàn toàn phân biệt ~a, b, c~ lần lượt là vị trí của chó, mèo và chuột. Hãy cho biết vị trí của chó cần đi tới.

Input

Dòng 1 chứa hai số nguyên dương ~n, m~ (~3 ≤ n ≤ 10^5; m ≤ 10^5~)

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ứng với một cạnh ~(u, v)~ trên cây

~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên hoàn toàn phân biệt ~a, b, c~ ứng với một bộ vị trí của chó, mèo và chuột

Output

Ghi ra ~m~ dòng, mỗi dòng ghi số hiệu đỉnh là câu trả lời cho một truy vấn.

Test mẫu

Input

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

Output

1
3
5
3