Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~L~ tới phần tử thứ ~R~ là bao nhiêu ~( a_l, a_{l+1}, ..., a_{r-1}, a_r )~

Input

• Một số nguyên duy nhất là ~T (1 \leq T \leq 5)~ testcase và ~T~ khối tiếp theo gồm:
  • Hai số nguyên là ~N, Q(1 \leq N, Q \leq 10^5)~, đại diện cho số phần tử của mảng ~A~ và số truy vấn
  • Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
  • Và ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R( 1 \leq L \leq R \leq N,)~, đại diện cho truy vấn từ ~L~ tới ~R~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

5
6
5

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~L~ tới phần tử thứ ~R~ là bao nhiêu ~( a_l, a_{l+1}, ..., a_{r-1}, a_r )~

Input

• Hai số nguyên là ~N, Q(1 \leq N, Q \leq 10^5)~, đại diện cho số phần tử của mảng ~A~ và số truy vấn
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
• Và ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R( 1 \leq L \leq R \leq N,)~, đại diện cho truy vấn từ ~L~ tới ~R~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

3 2
1 2 3
1 2
1 3

Sample Output

3
6

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~N~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~1~ tới phần tử thứ ~i~ là bao nhiêu ~( a_1, a_2, ..., a_{i-1}, a_i )~

Input

• Hai số nguyên là ~N(1 \leq N \leq 10^5)~, đại diện cho số phần tử của mảng ~A~
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.

Output

• Gồm ~N~ số nguyên ~a_i~ đại diện cho tổng các số từ ~1~ tới ~i~

Sample Input

4
1 2 3 4

Sample Output

1 3 6 10

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~1~ tới phần tử thứ ~x~ là bao nhiêu ~( a_1, a_{1+1}, ..., a_{x-1}, a_x )~

Input

• Số nguyên là ~N (1 \leq N \leq 10^5)~, đại diện cho số phần tử của mảng ~A~.
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
• Số nguyên ~Q (1 \leq Q \leq 10^5)~, là số lượng câu hỏi.
• Và ~Q~ dòng tiếp theo gồm 1 số nguyên duy nhất ~x( 1 \leq x \leq N)~, đại diện cho truy vấn từ ~1~ tới ~x~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

3
1 2 3
2
3
2

Sample Output

6
3

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng hai chiều ~A~ có ~N \times M~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số trong hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~ là bao nhiêu

Input

• Hai số nguyên là ~N, M(1 \leq N, M \leq 10^3)~, đại diện cho số hàng và số cột của mảng ~A~
• Dòng tiếp theo gồm ~N~ hàng và mỗi hàng có ~M~ phần tử ~a_{i,j}( 1 \leq i \leq N, 1 \leq j \leq M, 1 \leq a_{i,j} \leq 10^9 )~ của mảng ~A~.
• Dòng tiếp theo có duy nhất 1 số nguyên ~Q~, đại diên cho số truy vấn
• Và ~Q~ dòng tiếp theo với mỗi dòng gồm 4 số nguyên ~x_1, y_1, x_2, y_2( 1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M )~, đại diện cho truy vấn hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

18

Cho một mảng gồm ~n~ số nguyên dương, nhiệm vụ của bạn là đếm số lượng mảng con liên tiếp có tổng các phần tử chính xác bằng ~x~.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 2 \times 10^{5} ; 1 \le x \le 10^{9})~ ~-~ số lượng phần tử trong mảng và mục tiêu tổng ~x~.

Dòng tiếp theo gồm ~n~ số nguyên ~a_{1}, a_{2},..., a_{n}~ ~(1 \le a_{i} \le 10^{9})~ ~-~ giá trị của các phần tử trong mảng đã cho.

Output

Một số nguyên duy nhất là số lượng mảng con đếm được.

Sample Input

5 7
2 4 1 2 7

Sample Output

3

Giải thích

Có ~3~ mảng con thỏa mãn, đó là: ~[1, 3], [2, 4], [5, 5]~.

Cho một dãy số gồm ~n~ phần tử ~a_1,a_2,...a_n~ và ~q~ truy vấn ~l~, ~r~ ~(1 \le l \le r \le n)~. Yêu cầu kiểm tra tổng trong đoạn ~[l;r]~ có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n \le 10^{4}; 1 \le q \le 10^{6})~. Độ dài của mảng và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...a_n~ ~(1 \le a[i] \le 10^{3})~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l~, ~r~ , tương ứng với truy vấn thứ ~i~. Yêu cầu kiểm tra tổng từ ~[l;r]~ có phải là số nguyên tố hay không?

Output

• In ra ~q~ dòng tương ứng với câu trả lời thứ ~i~. In YES nếu tổng là số nguyên tố, ngược lại in NO.

Sample Input 1

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

Sample Output 1

NO
YES
YES
NO

Cho một dãy số gồm ~n~ phần tử ~a_1,a_2,...a_n~ và ~q~ truy vấn ~l~, ~r~ ~(1 \le l \le r \le n)~. Yêu cầu kiểm tra tổng trong đoạn ~[l;r]~ có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^{3})~. Độ dài của mảng và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...a_n~ ~(1 \le a[i] \le 10^{3})~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l~, ~r~ , tương ứng với truy vấn thứ ~i~. Yêu cầu kiểm tra tổng từ ~[l;r]~ có phải là số nguyên tố hay không?

Output

• In ra ~q~ dòng tương ứng với câu trả lời thứ ~i~. In YES nếu tổng là số nguyên tố, ngược lại in NO.

Sample Input 1

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

Sample Output 1

NO
YES
YES
NO

Mô tả

Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~. Với mỗi truy vấn, bạn cần tính tổng các số nguyên tố trong đoạn ~[L,R]~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ ~-~ số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~.

Output

Gồm ~Q~ dòng, mỗi dòng ứng với mỗi truy vấn, in ra một số duy nhất là tổng các số nguyên tố trong đoạn ~[L,R]~.

Ví dụ

Input

3
1 10
5 15
1 5

Output

17
36
10

Giải thích

• Truy vấn 1: Các số nguyên tố trong đoạn ~[1,10]~ là ~2, 3, 5, 7~. Tổng ~= 17~.
• Truy vấn 2: Các số nguyên tố trong đoạn ~[5,15]~ là ~5, 7, 11, 13~. Tổng ~= 36~.
• Truy vấn 3: Các số nguyên tố trong đoạn ~[1,5]~ là ~2, 3, 5~. Tổng ~= 10~.

Sau những ngày chinh chiến với CP, anh Phú về quê nghỉ dưỡng một thời gian và trồng hoa cùng chị. Vườn hoa của anh Phú có kích thước ~m \times n~ và trồng nhiều loại hoa có chiều cao nhất định. Nhưng vì vườn hơi rộng nên chị muốn chọn ra một phần trong vườn có kích thước ~h \times w~ để chăm sóc cho dễ, kịp đón Tết. Để phần vườn đó đẹp nhất, các cây hoa phải có chiều cao bằng nhau và Phú cần phải chọn ra một giá trị chiều cao ~x~ nào đó rồi thực hiện các thao tác: nếu trong phần vườn đang chọn, có hoa cao hơn ~x~ thì Phú sẽ đào đất sâu hơn để trồng cho hoa thấp vừa bằng ~x~; còn nếu hoa thấp hơn ~x~ thì Phú lại đắp đất cao hơn để hoa cao vừa bằng ~x~. Mỗi đơn vị chênh lệch chiều cao sẽ tốn của Phú thời gian không nhỏ, vì thế nên bạn sẽ chọn ra giá trị ~x~ để tiết kiệm công sức nhất có thể.

Biết Phú vất vả nên chị cũng muốn tính toán xem trong các cách chọn vị trí phần vườn thì giá trị ~x~ tương ứng có thể nhỏ nhất là bao nhiêu. Bạn hãy giúp chị trả lời câu hỏi này nhé.

Input

Dòng đầu tiên gồm 4 số nguyên ~m, n, h, w~ cho biết kích thước liên quan, trong đó ~1 \le h \le m \le 10^3~ và ~1 \le w \le n \le 10^3.~

Trong các dòng tiếp theo, ta có thông tin về chiều cao các bông hoa trong vườn chị, giá trị nguyên không âm và không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

5 6 3 3
89 53 45 1 1 76
76 77 66 73 76 53
1 71 91 17 55 61
91 19 9 29 21 89
11 21 81 81 61 81

Sample output

21

Giải thích: ta có thể chỉ ra được nếu chọn phần vườn ~3 \times 3~ ở góc dưới bên trái thì giá trị ~x~ Phú sẽ chọn là ~21~, và chứng minh được số này là nhỏ nhất có thể.

Subtasks

• Có 20% số test có ~m, n ≤ 30~
• Có 20% số test có ~m, n ≤ 100~
• Có 30% số test có ~m, n≤ 300;~
• Có 30% số test có giới hạn như dữ kiện bài ra.

Cho dãy ký tự ~S~ chứa ~n \le 10^5~ ký tự thuộc tập ~\{'H', 'S', 'G' \}~. Đếm số dãy con ~S'~ của ~S~ sao cho trong ~S'~, số lượng ký tự mỗi loại ít nhất là ~2.~

Input

Một dòng duy nhất là chuỗi ký tự.

Output

Đáp số của bài toán.

Sample input

HHHSSSSGGG

Sample output

4

Giải thích

Có 4 chuỗi con thỏa mãn tính trong các vị trí: (2,11), (2, 12), (1,11), (1,12).

(Trích đề thi phỏng vấn Senior Dev lương 2000$)

Có một dãy ~n~ bóng đèn đánh số từ ~1~ đến ~n~ được nối với nhau thành một dãy. Có ~n~ thao tác: trong thao tác thứ ~i~ sẽ cho biết số thứ tự của bóng đèn được bật công tắc trong lần thứ ~i~. Biết rằng một bóng đèn được bật công tắc thì chưa hẳn nó sẽ sáng, cần phải có tất cả các bóng đèn có số thứ tự nhỏ hơn nó cũng đều được bật công tắc thì mới đảm bảo (theo nguyên lý mạch điện mắc nối tiếp). Yêu cầu đặt ra là đếm số thời điểm mà mọi bóng đèn được bật thì đều sáng.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Dòng tiếp theo là ~n~ số nguyên dương phân biệt có giá trị từ ~1~ đến ~n~ sắp xếp theo thứ tự nào đó, cho biết số thứ tự của các bóng đèn được bật.

Output

Đáp số của bài toán.

Sample input

5
2 1 3 5 4

Sample output

3

Giải thích: ta thấy lần đầu thì dù bóng đèn số 2 được bật, nhưng bóng 1 chưa bật thì bóng 2 vẫn chưa sáng; đến lần tiếp theo thì bóng 1 đã được bật thì cả 2 bóng 1, 2 đều sáng, tính một lần. Cứ thế, ta thấy các bóng sẽ sáng ngay thời điểm bật bao gồm: ~2, 3, 5.~

Thầy Luna xếp các SV của CLB thành một hàng dọc để cho ba leader Trung, Nhân, Phú đi kiểm tra. Đi từ đầu dãy:

• Nếu tổng số nam hiện tại lớn hơn số nữ thì sẽ cho Trung ~1~ món quà;

• Nếu tổng số nữ hiện tại lớn hơn số nam thì sẽ cho Nhân ~1~ món quà;

• Nếu tổng số nam hiện tại bằng số nữ thì sẽ cho Phú ~1~ món quà;

Tính số món quà của mỗi bạn leader nhận được.

Input.

Một dòng duy nhất gồm một chuỗi chứa ký tự 'B', 'G' cho biết vị trí của các nam nữ. Độ dài của chuỗi không vượt quá ~10^5.~

Output.

Một dòng duy nhất gồm ba số cho biết số món quà của Trung, Nhân, Phú.

Sample input.

BGBGG

Sample output.

2 1 2

Vào đợt khai giảng năm học mới, CLB lập trình có ra chiến dịch tuyển thành viên theo cách sau đây: mỗi SV muốn tham gia thì cần thi 3 bài: lập trình C/C++, kiểm tra tư duy logic và kiểm tra tiếng Anh. Điểm của mỗi người sẽ là ba số nguyên dương không vượt quá 1 tỷ. Với điểm thi ở một môn nào đó của một thí sinh ~X~ bất kỳ, ta định nghĩa "độ thua kém" so với thí sinh ~Y~ (cũng ở môn đó) là số điểm mà ~Y~ hơn ~X~, trong trường hợp ~X~ cao điểm hơn ~Y~ thì độ thua kém là ~0.~

Ví dụ: ở môn lập trình C/C++, nếu ~X~ đạt 7đ, ~Y~ đạt 9đ còn ~Z~ đạt 6đ thì ~X~ thua kém ~Y~ là 2đ nhưng thua kém ~Z~ là 0đ.

Tuy nhiên, bài kiểm tra là rất khó và hầu như các bạn đạt điểm rất thấp, không như mong muốn của CLB. Vì thế CLB đã đề xuất ra một khóa huấn luyện cho "thành viên dự bị" với chi phí được tính như sau: với mỗi ứng viên ~X~, chi phí mà ~X~ cần nộp bằng với giá trị lớn nhất của tổng độ thua kém ở cả ba môn so với từng ứng viên còn lại (đọc thêm VD minh họa để hiểu rõ hơn).

Bạn Vuvuzela, một thủ quỹ của CLB, muốn dựa vào kết quả thi của các thành viên, tính ra xem số tiền ít nhất và nhiều nhất mà các ứng viên cần nộp là bao nhiêu. Hãy giúp Vuvuzela thực hiện điều này nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 2 \cdot 10^5.~

Trong ~n~ dòng tiếp theo, mỗi dòng là một bộ ba điểm thi của các ứng viên.

Output

Số tiền nhiều nhất, ít nhất mà một ứng viên phải đóng.

Các subtasks trong bài:

• Có 50% điểm ứng với ~n \le 2023~ và các điểm số không vượt quá ~10^3.~
• Có 50% điểm ứng với ~2024 \le n \le 2 \cdot 10^5~ và các điểm số không vượt quá ~10^9.~

Sample input

3
6 7 8 
5 10 5
8 8 8

Sample output

6 2

Giải thích: Ta tính được chi phí mà các ứng viên phải đóng lần lượt là:

• Độ thua kém của 1 so với 2 là: ~0+3+0=3~; so với 3 là ~2+1+0=3~ nên chi phí là ~\max(3,3)=3~.
• Độ thua kém của 2 so với 1 là: ~1+0+3=4~; so với 3 là ~3+0+3=6~ nên chi phí là ~\max(4,6)=6~.
• Độ thua kém của 3 so với 1 là: ~0+0+0=0~; so với 2 là ~0+2+0=2~ nên chi phí là ~\max(2,2)=2~.

Do đó, ứng viên 2 phải đóng nhiều nhất, đến 6 đồng, còn ứng viên 3 đóng ít nhất, 2 đồng.