Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Vào năm ~2069~, để khuyến khích các thành đua top điểm, VNOJ đã tổ chức event trong ~q~ ngày: vào ngày thứ ~i~, với mỗi ~k_i~ bài tập giải được, user sẽ được gấp đôi số điểm cho bài tập thứ ~k_i + 1~ (bài tập này sẽ không tính vào ~k_i~ bài tập tiếp theo). Lúc này, hệ thống VNOJ có ~n~ bài tập, bài tập thứ ~i~ nếu giải đúng sẽ được ~p_i~ điểm.

lastPledge quyết định làm bài trên VNOJ để giải trí sau những giờ chơi game căng thẳng. Tuy nhiên vì đang bận leo rank LMHT, lastPledge chỉ có thể chọn ~1~ trong ~q~ ngày để leo rank VNOJ. Biết rằng vào ngày thứ ~i~, tâm trạng của lastPledge cho phép anh ấy giải tối đa ~c_i~ bài tập. lastPledge muốn tính xem làm bài vào ngày nào thì sẽ được nhiều điểm nhất, vì vậy anh ấy muốn biết: nếu giải bài vào ngày thứ ~i~, anh ấy sẽ nhận được tối đa bao nhiêu điểm.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ (~1 \le n \le 10^6~) – số bài tập trên VNOJ và ~q~ (~1 \le q \le 10^6~) - số ngày diễn ra event trên VNOJ.

Dòng thứ hai gồm ~n~ số nguyên dương ~p_1, p_2, \ldots, p_n~ ~(1 \le p_i \le 10^9)~ – số điểm nhận được nếu giải bài thứ ~i~.

~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~c_i~ và ~k_i~ (~1 \le c_i, k_i \le n~) thể hiện ngày thứ ~i~ của event trong đề bài.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra số điểm tối đa lastPledge nhận được nếu giải bài vào ngày thứ ~i~.

Subtask

  • ~50\%~ số test có ~n \le 10^3~.

  • ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

29
38
18

Notes

Vào ngày thứ ~1~, lastPledge có thể chọn giải bài theo thứ tự ~[3, 1, 2, 4]~. Số điểm anh ấy nhận được là ~6 + 4 + 7 \cdot 2 + 5 = 29~.

Vào ngày thứ ~2~, lastPledge có thể chọn giải bài theo thứ tự ~[4, 3, 5, 2, 1]~. Số điểm anh ấy nhận được là ~5 + 6 \cdot 2 + 3 + 7 \cdot 2 + 4 = 38~.

Vào ngày thứ ~3~, lastPledge có thể chọn giải bài theo thứ tự ~[3, 4, 2]~. Số điểm anh ấy nhận được là ~6 + 5 + 7 = 18~.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Một dãy số ~b_1, b_2, \ldots, b_k~ được gọi là hoàn hảo nếu các phần tử của dãy ~b~ tạo thành một dãy số nguyên liên tiếp khi sắp xếp tăng dần.

Cho hoán vị ~p_1, p_2, \ldots, p_n~ và ~q~ truy vấn có dạng ~(l, r)~, hãy cho biết dãy con ~p_l, p_{l + 1}, \ldots, p_r~ có phải là dãy số hoàn hảo hay không?

Input

Dòng đầu tiên gồm số nguyên ~n~ (~1 \le n \le 10^5~) — độ dài của hoán vị ~p~ và ~q~ (~1 \le q \le 10^5~) — số truy vấn của bài toán.

Dòng thứ hai gồm ~n~ số nguyên dương ~p_1, p_2, \ldots, p_n~ (~1 \le p_i \le n~) thể hiện hoán vị ~p~ độ dài ~n~.

~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~(l_i, r_i)~ (~1 \le l_i \le r_i \le n~) thể hiện một truy vấn của bài toán.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra YES nếu dãy con ~p_{l_i}, p_{l_i + 1}, \ldots, p_{r_i}~ là một dãy số hoàn hảo; ngược lại in ra NO.

Subtask

  • ~30\%~ số test có ~n \le 300~.

  • ~30\%~ số test khác có ~n \le 5000~.

  • ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

NO
YES
NO
YES

Notes

Ở truy vấn thứ nhất, dãy con ~[1, 2, 5]~ không phải là dãy số hoàn hảo.

Ở truy vấn thứ hai, dãy con ~[2, 5, 3, 4]~ là dãy số hoàn hảo vì khi sắp xếp lại, ta nhận được dãy ~[2, 3, 4, 5]~ là một dãy số nguyên liên tiếp.

Ở truy vấn thứ ba, dãy con ~[1, 2, 5, 3]~ không phải là dãy số hoàn hảo vì khi sắp xếp lại, ta nhận được dãy ~[1, 2, 3, 5]~ không phải là dãy số nguyên liên tiếp.

Ở truy vấn thứ tư, dãy con ~[5]~ là dãy số hoàn hảo.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

FireGhost130104 được bạn tặng xâu nhị phân ~s~ có độ dài ~n~. Vì chưa cảm thấy hài lòng với độ đẹp của xâu ~s~, FireGhost dự định tạo ra xâu ~t~ bằng cách thực hiện các thao tác sau:

  • Gọi độ dài hiện tại của xâu ~s~ là ~m~. FireGhost sẽ chọn ngẫu nhiên số ~k~ trong khoảng ~[1, m]~.

  • FireGhost lấy xâu tiền tố độ dài ~k~ của xâu ~s~ ra khỏi xâu ~s~.

  • Nếu kí tự đầu của xâu tiền tố là ~0~, FireGhost sẽ lật toàn bộ xâu tiền tố đó lại (đổi ~0~ thành ~1~ và ngược lại).

  • Sau đó, FireGhost sẽ thêm xâu tiền tố đó vào cuối xâu ~t~.

  • Tiếp tục thực hiện cho đến khi xâu ~s~ rỗng.

Ví dụ về một khả năng xảy ra khi ~s = 1001011~:

  • Ở bước đầu tiên, FireGhost chọn ~k = 4~. Anh ấy lấy ra xâu tiền tố ~1001~. Vì kí tự đầu của xâu tiền tố này là ~1~ nên xâu tiền tố không thay đổi. Sau đó, FireGhost sẽ thêm xâu tiền tố này vào cuối xâu ~t~. Lúc này, ~s = 011~, ~t = 1001~.

  • Ở bước thứ hai, FireGhost chọn ~k = 3~. Anh ấy lấy ra xâu tiền tố ~011~. Vì kí tự đầu của xâu tiền tố này là ~0~ nên xâu tiền tố này sẽ bị lật thành ~100~. Sau đó, FireGhost sẽ thêm xâu tiền tố này vào cuối xâu ~t~. Lúc này, ~s = \emptyset~, ~t = 1001100~.

Gọi độ đẹp của một xâu là số kí tự ~1~ nằm trong xâu đó.

Vì xâu ~t~ nhận được là ngẫu nhiên nên FireGhost không biết liệu độ đẹp của xâu ~t~ có tốt hơn xâu ~s~ hay không, hãy giúp FireGhost tính giá trị kì vọng của độ đẹp xâu ~t~ nhé!

Gọi ~X = [k_1, k_2, ..., k_c]~ là tập hợp độ dài các thao tác lần lượt thực hiện; ~f(X)~ là độ đẹp của xâu ~t~ nhận được sau khi thực hiện các thao tác trong ~X~; ~g(X)~ là xác suất thực hiện các thao tác trong ~X~. Gọi ~P~ là tập hợp chứa tất cả các tập hợp các thao tác có thể xảy ra. Giá trị kì vọng của độ đẹp xâu ~t~ được tính bằng ~\sum_{X \in P} f(X) \cdot g(X)~.

Input

Dòng đầu tiên gồm số nguyên ~n~ (~1 \le n \le 5 \cdot 10^5~) - độ dài của xâu ~s~.

Dòng thứ hai gồm xâu nhị phân ~s~ độ dài ~n~.

Output

In ra một dòng duy nhất là giá trị kì vọng của độ đẹp xâu ~t~. Đáp án của bạn sẽ được chấp nhận nếu sai số không vượt quá ~10^{-9}~. Nói cách khác, gọi đáp án của bạn là ~a~, đáp án của jury là ~b~, đáp án của bạn sẽ được chấp nhận nếu ~\frac{|a - b|}{max(1,\ |b|)} \le 10^{-9}~.

Subtask

  • ~20\%~ số test có ~n \le 20~.

  • ~30\%~ số test khác có ~n \le 5000~.

  • ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
011

Sample Output 1

2.000000000000000

Sample Input 2

5
01010

Sample Output 2

3.266666666666667

Notes

Trong test ví dụ thứ nhất, xét tất cả các tập hợp độ dài có thể xảy ra:

  • ~[1, 1, 1]~: FireGhost nhận được xâu ~t = 111~. Độ đẹp của xâu ~t~ là ~3~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{2} \cdot \frac{1}{1} = \frac{1}{6}~.

  • ~[1, 2]~: FireGhost nhận được xâu ~t = 111~. Độ đẹp của xâu ~t~ là ~3~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{2} = \frac{1}{6}~.

  • ~[2, 1]~: FireGhost nhận được xâu ~t = 101~. Độ đẹp của xâu ~t~ là ~2~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{1} = \frac{1}{3}~.

  • ~[3]~: FireGhost nhận được xâu ~t = 100~. Độ đẹp của xâu ~t~ là ~1~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3}~.

Vì vậy, giá trị kì vọng của độ đẹp xâu t là ~3 \cdot \frac{1}{6} + 3 \cdot \frac{1}{6} + 2 \cdot \frac{1}{3} + 1 \cdot \frac{1}{3} = 2~.


Giới hạn thời gian: 3.0s / Giới hạn bộ nhớ: 512M

Điểm: 100

Đất nước Gluville là một trong những nơi du lịch nổi tiếng nhất từng được biết đến. Vào một ngày nọ, Rishan và gia đình của anh ấy quyết định đến tham quan Gluville một chuyến.

Gluville gồm ~n~ thành phố được nối với nhau bởi ~n-1~ con đường hai chiều. Các con đường này đảm bảo rằng bất kỳ ~2~ thành phố nào trong Gluville đều đến được với nhau. Con đường thứ ~i~ có độ dài là ~w_i~ nối ~2~ thành phố ~u_i~ và ~v_i~. Rishan đã tìm hiểu và biết được rằng mỗi khi đi từ thành phố này qua thành phố khác thì phải tốn ~1~ đồng xu để nộp cho trạm gác. Do đó, chi phí di chuyển sẽ được tính bằng tổng đồng xu trả cho trạm gáctổng độ dài đường đi trên đường đi ngắn nhất từ ~u~ đến ~v~.

Rishan đã tìm được ~q~ tour du lịch khác nhau cho chuyến đi. Tour thứ ~i~ gồm ~k_i~ thành phố khác nhau ~u_1,u_2,\dots,u_{k_i}~. Vì thời gian có hạn, Rishan muốn lên kế hoạch kĩ càng cho cuộc hành trình của mình. Cậu ấy muốn biết chi phí di chuyển lớn nhất giữa ~2~ thành phố bất kỳ trong ~k_i~ thành phố của tour thứ ~i~. Hãy giúp Rishan!

Input

  • Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~q~ ~(2 \le n \le 10^6;1 \le q \le 5\times 10^5)~.

  • ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~u_i,v_i,w_i~ thể hiện một con đường nối giữa thành phố ~u_i~ và ~v_i~ có độ dài là ~w_i~ ~(1 \le w_i \le 10^9)~.

  • ~q~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~k_i~ ~(2 \le k_i \le n)~ là số thành phố của tour thứ ~i~, tiếp theo đó là ~k_i~ đỉnh phân biệt được ngăn cách bởi dấu cách.

    Đảm bảo rằng ~\sum_{i=1}^{q}k_i \le n~.

Output

  • Gồm ~q~ dòng là đáp án của ~q~ truy vấn theo thứ tự.

Subtask

  • ~30\%~ số test có ~q = 1, \sum_{i = 1}^{q}k_i \le 1000~.

  • ~60\%~ số test có ~n, q, \sum_{i = 1}^{q}k_i \le 2\times 10^5~.

  • Số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

10
15

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Hôm nay kuroni được học về tổ hợp tuyến tính. Trước khi kết thúc buổi học, thầy giáo ra một câu đố như sau:

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một số nguyên dương ~x~ được gọi là đẹp nếu tồn tại một bộ ~n~ số nguyên không âm ~v_1, v_2, ..., v_n~ thỏa mãn ~x = a_1 \cdot v_1 + a_2 \cdot v_2 + \cdots + a_n \cdot v_n~.

Gọi ~b~ là tập hợp tất cả các số đẹp sắp xếp theo thứ tự tăng dần. Thầy giáo có ~q~ câu hỏi, mỗi câu hỏi thầy giáo yêu cầu học sinh tìm giá trị của số thứ ~k~ trong dãy ~b~.

Cả lớp đang im lặng vì gặp câu hỏi khó, bỗng kuroni thấy buồn đi vệ sinh. Anh ấy đứng lên, giơ tay nói to: "Em..." Chưa kịp nói dứt câu, thầy giáo đã mừng rỡ, ngay lập tức gọi kuroni lên bảng. Không muốn mất mặt trước cả lớp mà tình thế lại vô cùng cấp bách, anh ấy đã cầu cứu bạn cùng bàn. Hãy trợ giúp kuroni trả lời các câu hỏi của thầy nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 3 \cdot 10^5~) — độ dài của dãy ~a~ và ~q~ (~1 \le q \le 3 \cdot 10^5~) — số câu hỏi của thầy giáo.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6, \sum_{i = 1}^n a_i \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~k~ mô tả các câu hỏi của thầy giáo ~(1 \leq k \leq 10^9)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho câu hỏi thứ ~i~.

Subtask

  • ~5\%~ số test có ~n = 1~.

  • ~10\%~ số test khác có ~1 \leq a_1, a_2, ...,a_n \leq 10~.

  • ~15\%~ số test khác có ~k \leq 5000~ trong mọi câu hỏi.

  • ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 8
5 3 11
1
2
8
9
6
5
14
23

Sample Output 1

3
5
12
13
10
9
18
27

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 512M

Điểm: 100

Naot là một người vô cùng yêu thích món trà sữa, một thức uống lâu đời với hương thơm thanh nhã đặc trưng của trà và vị ngọt béo thơm ngon của sữa. Dù tròn vị yêu thương, thơm ngon tròn vị là thế; nhưng trà sữa lại không tốt cho sức khỏe, thức uống này mang quá nhiều năng lượng; do đó Naot phải rất hạn chế sử dụng loại thức uống yêu thích này.

Theo một nghiên cứu gần đây được đăng trên tạp chí một khoa học không chính thống, nếu tổng lượng calo trà sữa tiêu thụ chia hết cho ~n~, ta có thể coi như chưa từng uống trà sữa. Đọc được nghiên cứu này, Naot lập tức muốn biết liệu ông có bao nhiêu cách để uống trà sữa mà có thể coi như chưa từng uống.

Cụ thể, ông uống trà sữa liên tục trong ~k~ ngày; mỗi ngày ông mua về ~n~ cốc trà sữa có hàm lượng calo lần lượt là ~1,2,3,...,n~; mỗi cốc trà sữa mua về có thể uống hoặc không. Ông muốn tính xem có bao nhiêu cách uống trà sữa mà sau ~k~ ngày, có thể coi như ông chưa từng uống trà sữa.

Yêu cầu: Bạn hãy giúp Naot tính số lượng cách nhé, vì đáp án có vẻ rất lớn, hãy in ra số cách chia dư cho ~5600748293801~.

Input

Dòng đầu tiên gồm một số nguyên dương t (~1\le t \le 10~) - Số bộ test cần giải trong bài toán này.

Mỗi bộ test gồm một dòng duy nhất chứa ~2~ số nguyên dương lần lượt là ~n~ và ~k~ (~1\le n\le 10^{12}, 1\le k \le 10^{18}~).

Dữ liệu đảm bảo tổng của ~n~ trong tất cả bộ test không quá ~10^{12}~.

Output

Với mỗi bộ test, in ra trên một dòng là kết quả của bài toán chia dư cho ~5600748293801~.

Subtask

  • ~10\%~ số test có ~t=1, n \cdot k \leq 20~.

  • ~20\%~ số test khác có ~n, k \le 500~.

  • ~20\%~ số test khác có ~n \le 1000~.

  • ~30\%~ số test khác có ~n \le 10^6~.

  • Số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
5 1
6 1
3 2
2 5
6 2

Sample Output 1

8
12
24
512
688

Notes

Trong bộ test đầu tiên, các cách uống tà tưa thỏa mãn là: ~\{\}, \{2, 3\}, \{1, 4\}, \{1, 2, 3, 4\}, \{5\}, \{2, 3, 5\}, \{1, 4, 5\}, \{1, 2, 3, 4, 5\}~

Trong bộ test thứ hai, các cách uống trà sữa thỏa mãn là:

~\{\}~

~\{1, 2, 3\}~

~\{2, 4\}~

~\{1, 5\}~

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

~\{3, 4, 5\}~

~\{6\}~

~\{1, 2, 3, 6\}~

~\{2, 4, 6\}~

~\{1, 5, 6\}~

~\{1, 2, 4, 5, 6\}~

~\{3, 4, 5, 6\}~