Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong hai số: ~3~ hoặc ~5~.

Ví dụ về dãy các số đẹp: ~3, 5, 6, 9, 10, 12, 15, 18, 20,...~

Hãy tìm số đẹp thứ ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~k~.

Output

• In ra kết quả của bài toán.

Giới hạn:

• Subtask 1 (~50\%~ số điểm): ~k \le 10^6~
• Subtask 2 (~50\%~ số điểm): ~k \le 10^{12}~

Sample Input 1

2

Sample Output 1

5

Sample Input 2

10

Sample Output 2

21

Cho một dãy ~a~ gồm ~n~ phần tử và số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ thỏa mãn ~i < j~ và ~a_i + a_j \le k~.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~n~ và ~k~.
• Dòng thứ hai gồm ~n~ phần tử nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^6)~

Output

• In ra kết quả của bài toán.

Giới hạn:

• Subtask 1 (~50\%~ số điểm): ~n \le 5000~
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~

Sample Input 1

4 6
1 3 5 6

Sample Output 1

2

Sample Input 2

6 8
1 2 5 3 4 8

Sample Output 2

9

Cho ~2~ mảng ~a~ và ~b~ đều gồm ~n~ số nguyên dương và một số nguyên dương ~k~. Mảng số nguyên ~c~ gồm ~n^2~ phần tử được xây dựng bằng cách với mỗi cặp ~i,j~ thỏa mãn ~1 \le i,j \le n~, ta gán giá trị ~c_{(i-1)*n+j} = a_i + b_j~.

Sắp xếp mảng ~c~ lại theo thứ tự không giảm, hãy in ra số thứ ~k~ trong dãy ~c~ mới.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~.
• Dòng tiếp theo gồm ~n~ số nguyên dương mô tả dãy ~a~.
• Dòng cuối cùng gồm ~n~ số nguyên dương mô tả dãy ~b~.

Output

• In ra kết quả của bài toán.

Constraints

• ~1 \le n \le 10^5~, ~1 \le k \le n^2~.
• ~1 \le a_i,b_i \le 10^9~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

9

Cho một xâu ~s~ có độ dài ~n~ chỉ bao gồm các kí tự ~a,b,c~. Một đoạn ~[l,r]~ được gọi là tốt khi và chỉ khi có một kí tự trong đoạn có số lần xuất hiện lớn hơn một nửa độ dài đoạn. Nói cách khác, gọi ~cnt(d,l,r)~ là số lần xuất hiện của kí tự ~d~ trong đoạn ~[l,r]~, ta cần tồn tại một kí tự ~d~ trong đoạn ~[l,r]~ sao cho ~cnt(d,l,r) > (r-l+1)/2~. (Với ~d~ thuộc ~[a,b,c]~)

Hãy in ra độ dài đoạn tốt lớn nhất.

Input

• Dòng đầu gồm số nguyên dương ~n~ miêu tả độ dài xâu. ~(1 \le n \le 10^5)~
• Dòng thứ hai miêu tả xâu ~s~. Xâu ~s~ chỉ bao gồm các kí tự ~a,b,c~ và có độ dài ~n~.

• Ouput

• In ra độ dài đoạn tốt lớn nhất.

Sample Test

Input

7
aabbbcc

Output

5

Giải thích: Chọn đoạn ~[1,5]~.

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Cho một dãy số nguyên ~a~ gồm ~n~ ~(1 \le n \le 10^5, 1 \le a_i \le 10^6)~ phần tử và ~q~ ~(1 \le q \le 10^5)~ truy vấn. Mỗi truy vấn có dạng ~l,r~, hãy in ra tổng ~a_l,a_{l+1},..,a_r~.

Input

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

Output

3
5
15
7

Bạn được nhận ~n~ xâu kí tự, mỗi xâu gồm các chữ cái tiếng Anh in thường. Cần chọn ra một số xâu trong ~n~ xâu đó sao cho khi ghép tất cả chúng lại, ta được một xâu mới bao gồm đầy đủ các kí tự trong bảng chữ cái tiếng Anh. Hãy đếm số cách để thực hiện yêu cầu trên. Hai cách được coi là khác nhau khi có một xâu được chọn ở cách này không được chọn trong cách kia.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 25)~ miêu tả số lượng xâu.
• ~n~ dòng tiếp theo, mỗi dòng bao gồm một xâu kí tự ~S~ ~(|S| \le 30)~ gồm các chữ cái tiếng Anh in thường.

Output

• In ra một số nguyên là kết quả bài toán.

Sample Test

Input1:

8
the
quick
brown
fox
jumps
over
lazy
dog

Output1:

1

Input2:

3
a
b
abcdefghijklmnopqrstuvwxyz

Output2:

4

Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.

Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.

Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.

Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.

Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, không có khuyên và cạnh lặp.

Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương ~c~ trên mỗi đỉnh (~c~ chỉ có thể là ~1~, ~2~, hoặc ~3~), sao cho với mỗi cạnh, tổng của hai số được điền trên ~2~ đỉnh được kết nối bởi cạnh đó là một số lẻ.

Thỏ đố Rùa có thể đếm số cách để điền các số ~1,2,3~ lên mỗi đỉnh sao cho tạo ra được một đồ thị đẹp. Do con số này có thể rất lớn, hãy in nó ra theo ~modulo~ ~998244353~.

Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.

Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi ~q~ câu có dạng như vậy.

Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ miêu tả số câu hỏi.
• Đối với mỗi câu hỏi:
  • Dòng đầu tiên ~2~ số nguyên dương ~n,m~ miêu tả số đỉnh và cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n, u_i \neq v_i)~ miêu tả cạnh thứ ~i~.

Output

• Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho ~998244353~.

Điều kiện

• ~1 \le q \le 3 \times 10^5~.
• ~1 \le n,m \le 3 \times 10^5~.
• Dữ liệu đảo bảo rằng tổng ~n~ trong tất cả các câu hỏi không vượt quá ~3 \times 10^5~, tương tự với tổng ~m~.

Subtask

• ~50\%~ số điểm: ~n \le 10, q \le 10~.
• ~30\%~ số điểm: Trong mọi câu hỏi, đồ thị có dạng cây.
• ~20\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

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

Output:

0
4

Giải thích:

Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.

Ở câu hỏi thứ hai, có ~4~ cách điền như sau:

• Điền số ~1~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~3~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~1~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~3~ vào đỉnh ~2~.

Cho dãy số gồm ~n~ số nguyên ~c_1, c_2, …, c_n~ và số nguyên dương ~m~. Nhiệm vụ của bạn là tìm một đoạn ~b_1,b_2,...,b_k~ ~(1 \le b_1 < b_2 < ... < b_k \le n)~ sao cho ~(\sum c_{b_i}) \% m~ là lớn nhất có thể. Đoạn con tìm được có thể rỗng.

Yêu cầu: Hãy in ra giá trị lớn nhất tìm được.

Input

• Dòng đầu tiên chứa ~2~ số nguyên duyên ~n,m~
• Dòng thứ hai chứa dãy ~c~ gồm ~n~ phần tử.

Output

• Một số nguyên duy nhất là giá trị lớn nhất tìm được.

Constraints

• ~1 \le n \le 40~
• ~1 \le m \le 10^9~
• ~1 \le c_i \le 10^9~

Subtask

• Có ~50\%~ số test ứng với ~n \le 20~.
• Có ~50\%~ số test ứng với ~n \le 40~.

Sample Input 1

4 4
5 2 4 1

Sample Output 1

3

Sample Input 2

3 20
199 41 299

Sample Output 2

19

Cho một dãy ~a~ gồm ~n~ phần tử nguyên dương và hai giá trị nguyên dương ~k~, ~x~.

Ta có hàm ~cnt(l,r)~ là số các giá trị ~val~ xuất hiện nhiều hơn hoặc bằng ~x~ lần trong các phần tử thuộc đoạn ~[l,r]~ của dãy ~a~.

Hãy tìm một đoạn con có độ dài bằng ~k~ sao cho ~cnt(l,r)~ của nó là lớn nhất.

Input

• Dòng thứ nhất chứa ~3~ số nguyên dương ~n,k,x~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra giá trị của ~cnt(l,r)~ lớn nhất với ~r-l+1=k~.

Constraints

• ~1 \le x \le k \le n \le 2*10^5~.
• ~1 \le a_i \le 2*10^5~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

6 4 2
1 2 2 1 3 4

Sample Output 1:

2

Explanation 1:

Chọn đoạn ~[1,4]~.

Sample Input 2:

7 5 3
1 1 2 2 1 1 2 3

Sample Output 2:

1

Explanation 2:

Chọn đoạn ~[1,5]~.

Cho ~t~ truy vấn và giá trị ~mod~ ~(1 \le mod \le 2*10^9)~, mỗi truy vấn gồm hai số nguyên dương ~n~, ~k~. Kí hiệu ~C(k,n)~ là tổ hợp chập ~k~ của ~n~, hãy in ra ~C(k,n)~ cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho ~mod~.

Subtask

• Sub ~1~: ~t \le 10^5~, ~1 \le k \le n \le 2000~. (30%)
• Sub ~2~: ~t = 1~, ~1 \le k \le n \le 10^5~. (30%)
• Sub ~3~: ~t \le 10^5~, ~1 \le k \le n \le 10^5~, ~mod = 10^9+7~. (40%)

Input

• Dòng đầu tiên gồm một số nguyên dương ~sub~ miêu tả subtask mà test này tương ứng. (~1 \le sub \le 3~)
• Dòng thứ hai gồm hai số nguyên dương ~t~ và ~mod~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~, ~k~ (~k \le n~) miêu tả truy vấn tương ứng.

Output

• In ra ~t~ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Sample Test

Input:

1
3 2345
6 4
8 4
15 8

Output:

15
70
1745

Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình. Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, nếu đó là một cây thì in ra "Yes", ngược lại in ra "No".

Input:

• Dòng đầu gồm 2 số ~n~ và ~m~. ~(2 \le n, m \le 1e5).~
• ~m~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u, v \le n)~ chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.

Output:

• Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".

Sample Test 1

Input:

3 2
1 2
2 3

Output:

Yes

Sample Test 2

Input:

3 3 
1 2 
2 3 
3 1

Output:

No

Cho một cây vô hướng gồm ~n~ đỉnh, có gốc là đỉnh ~1~. Đỉnh ~i~ gồm một số ~a[i]~, nếu ~a[i] = 1~, nghĩa là có một chú mèo ở đỉnh ~i~, còn ngược lại thì không. Thinkies đang ở đỉnh ~1~, cậu chỉ có thể đi tới các đỉnh khác khi và chỉ khi từ đỉnh ~1~ tới đỉnh đó có số mèo trên các đỉnh liên tiếp nhỏ hơn hoặc bằng ~m~. Hãy đếm số đỉnh lá (các đỉnh không có đỉnh con) mà Thinkies có thể đi vào.

Input:

Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ (~1 \leq m \leq n \leq 10^5~).

Dòng sau gồm ~n~ số biểu thị dãy ~a~.

~n - 1~ dòng kế tiếp, mỗi dòng gồm 2 số ~u~ và ~v~, biểu thị có cạnh giữa 2 đỉnh ~u~ và ~v~.

Output:

In ra số lá mà Thinkies có thể đi vào

Mẫu:

Input:

4 1
1 1 0 0
1 2
1 3
1 4

Output:

2

Cho một cây có ~n~ đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n \le 10^5~.
• ~n - 1~ dòng tiếp theo chứa 2 số ~u, v (u, v \le n)~ là các cạnh của cây.

Output

• In ra một số nguyên số cạnh có thể xóa
• Nếu không thể có cách cắt thỏa mãn, in ra -1.

  Sample Test 1

Input:

4
2 4
4 1
3 1

Output:

1

Sample Test 2

Input:

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

Output:

4

Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có ~n~ đỉnh. Với mỗi đỉnh ~i~ cho 2 số ~l_i \le r_i~. Việc bạn cần làm là chọn một số ~v_i~ ở mỗi đỉnh sao cho ~l_i \le v_i \le r_i~ và số tiền được thưởng (tính bằng triệu VND) sẽ là tổng của ~|v_i - v_j|~ với toàn bộ các cạnh ~(i, j)~ vô hướng của cây. Hãy in ra số tiền nhiều nhất bạn có thể được thầy thưởng.

Input

• Dòng đầu tiên là số nguyên dương ~n \le 10 ^ 5~ là số đỉnh của cây.
• ~n~ dòng tiếp theo mỗi dòng ~i~ gồm 2 số ~l_i \le r_i \le 10^9~ là chỉ số của đỉnh thứ ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số ~u, v~ là cạnh của cây.

Output

• In ra một số là số tiền lớn nhất bạn có thể được thưởng.

Subtasks

• Subtask 1: ~n \leq 20~.
• Subtask 2: Với mỗi ~i < n~, tồn tại một cạnh ~i~ với ~i + 1~.
• Subtask 3: Không có điều kiện gì thêm.

Sample Test

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

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

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra ~m~ con búp bê của mình để thực hiện nhiệm vụ. Alice có ~n~ thùng đựng búp bê, thùng thứ ~i~ có ~a_i~ con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra ~m~ con búp bê.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m~ ~(1 \le m \le n \le 1000)~
• Dòng tiếp theo gồm ~n~ số tự nhiên là số lượng búp bê của từng thùng. (~1 \le a[i] \le 10^9~)

Output

• Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo ~10^9 + 7~

Sample Test

Input:

3 2
1 2 1

Output:

5

Giải thích:

• Có 5 cách chọn là: ~\{1, 2.1\}, \{1, 2.2\}, \{1, 3\}, \{2.1, 3\}, \{2.2, 3\}~ với ~x.y~ là con búp bê thứ ~y~ của thùng thứ ~x~

Cho dãy số gồm ~n~ ~(n \le 10^5)~ phần tử nguyên dương ~a_1, a_2, ... , a_n~ ~(a_i \le 10^6)~ và một số nguyên dương ~k~ cho trước ~(k \le 10^9)~

Tìm dãy con liên tiếp dài nhất có tổng đúng bằng ~k~

Input

• Dòng đầu nhập số nguyên dương ~n~ và ~k~.
• Dòng thứ ~2~ nhập ~n~ số nguyên ~a_1, a_2, ... , a_n~.

Output

• In ra kết quả là độ dài dãy con thỏa mãn yêu cầu

Sample test

Input

7 7 
4 3 2 1 1 1 6

Output

4

Cho số nguyên dương ~N~. Đếm xem có bao nhiêu cặp số nguyên ~[a,b]~ ~(0 < a \le b)~ để tổng các số nguyên trong đoạn ~[a,b]~ bằng ~N~. Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Input

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

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Subtask

• Subtask ~1~ (~40\%~ số điểm): ~n \le 10^4~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 10^8~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^{15}~

Sample Input 1

9

Sample Output 1

3

Explanation 1

~3~ đoạn thỏa mãn là : ~[2,4]~, ~[4,5]~, ~[9,9]~.

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử. Ta định nghĩa hàm ~f(l,r)~ như sau: ~f(l,r) = 1\times a[l] + 2\times a[l+1] + 3\times a[l+2] + ... (r-l+1)\times a[r]~.

Có ~q~ truy vấn, mỗi truy vấn gồm hai số ~l~, ~r~ với ~1 \le l \le r \le n~. Với mỗi truy vấn, hãy in ra ~f(l,r)~.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~q~. ~(1 \le n, q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l~, ~r~ miêu tả các truy vấn.

Ouput

• In ra ~q~ dòng, mỗi dòng là kết quả của một truy vấn tương ứng.

Subtask

• Subtask ~1~: ~n,q \le 2 \times 10^3~ ~(30\%)~
• Subtask ~2~: Trong tất cả các truy vấn, ~l=1~.
• Subtask ~3~: Không giới hạn gì thêm ~(40\%)~.

Sample Test

Input

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

Output

5
8
30

Cho số tự nhiên ~n~, hãy đếm bộ 3 số nguyên dương ~(a, b, c)~ sao cho ~a \times b \times c \le n~. Lưu ý ~(a, b, c)~ khác với ~(a, c, b)~ và tương tự.

Input

• Gồm số tự nhiên ~n \le 10^9~.

Output

• Số bộ số thỏa mãn.

Sample Test

Input:

3

Output:

7

Cho đồ thị vô hướng không có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Hãy đếm số thành phần liên thông của đồ thị đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả cạnh ~(u,v)~.

Output

• In ra số thành phần liên thông của đồ thị.

Điều kiện

• ~ 1 \le n,m \le 10^5~.

Ví dụ

Input 1:

4 3
1 2
2 3
3 4

Output 1:

1

Input 2:

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

Output 2:

2

Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

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

Output 1:

3 2 1

Input 2:

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

Output 2:

1 1 -1

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả kích thước bảng.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~

Ví dụ

Input 1:

3 4 
S...
....
...T

Output 1:

5

Input 2:

3 4 
S.*T
*.*.
*...

Output 2:

7

Năm ~1976~, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

• Không có khuyên.
• Đồ thị vô hướng.
• Đồ thị liên thông.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ ~0~ tới ~n-1~.
  • Dòng thứ hai gồm số nguyên dương ~m~ miêu tả số cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u,v~ miêu tả cạnh ~(u,v)~.

Output

• Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

• ~1 \le t \le 20~
• ~1 \le n,m \le 200~

Sample Input 1:

3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

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

Sample Output 1:

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1

Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6*10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t[1], t[2], ..., t[n]~.~(t[i] \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_[1], r_[2], ..., r_[n-1]~. ~(r[i] \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Trên dãy số nguyên ~a_1,a_2,...,a_n~ và với hai số nguyên ~w_1,w_2~, ta định nghĩa một bộ năm chỉ số ~1 \le i_1 < i_2 < ... < i_5 \le n~ được gọi là bộ năm và có trọng số được tính bằng: ~(w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_3 + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5})~.

Ví dụ, trên dãy gồm ~7~ số nguyên ~2,8,1,9,1,-1,8~ và ~w_1 = 1~, ~w_2 = -1~ thì bộ năm chỉ số ~2,3,4,6,7~ là một bộ năm có trọng số bằng ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times (-1)) + (1 \times 8) =25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số ~a_1,a_2,...,a_n~ và hai số nguyên ~w_1~ và ~w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,w_1,w_2~ ~(5 \le n \le 10^5; |w_1|, |w_2| \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output

• Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100~
• Có ~20\%~ số test ứng với ~w_1 = w_2 = 0~
• Có ~20\%~ số test ứng với ~n \le 5000, w_1 = 0~
• Có ~20\%~ số test ứng với ~w_1 = 0~
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

25

Sample Input 2

7 0 0
2 8 1 9 1 -1 8

Sample Output 2

9

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)