Thành phố của Bình có nhiều con đường được trồng cây xanh. Mỗi cây xanh được đặt tên bằng một chữ cái latinh hoa. Theo Bình, một đoạn đường được gọi là xanh đẹp nếu đoạn đường đó chỉ trồng một loại cây xanh (tức là trên đoạn đường đó, các cây được trồng ở vị trí liên tiếp, có tên giống nhau và thuộc một con đường).

Yêu cầu: Hãy giúp Bình tìm đoạn đường xanh đẹp gồm nhiều cây xanh nhất trong tất cả các con đường của thành phố.

Input

• Dòng ~1~ ghi số nguyên dương ~N (N \le 100)~ là số con đường trong thành phố.
• ~N~ dòng tiếp theo, mỗi dòng ghi một xâu kí tự gồm các chữ cái latinh hoa mô tả tên của các cây xanh được trồng liên tiếp từ đầu con đường đến cuối con đường. Số lượng cây trên mỗi con đường không lớn hơn ~10^4~.

Output

• In ra một số nguyên là số lượng cây xanh trên đoạn đường xanh đẹp gồm nhiều cây xanh nhất trong các con đường của thành phố.

Subtask

• Có ~80\%~ số test ứng với ~0 < N \le 10~ và số cây trên mỗi con đường không quá ~100~.
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
ABBBABAAH
HHHHHAHHHA
EEAE

Sample Output 1

5

Explanation 1

• Đoạn đường xanh đẹp gồm nhiều cây nhất là ~5~ cây ~(HHHHH)~ trong con đường thứ ~2~.

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

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 Input 1

8
the
quick
brown
fox
jumps
over
lazy
dog

Sample Output 1

1

Sample Input 2

3
a
b
abcdefghijklmnopqrstuvwxyz

Sample Output 2

4

Notes

Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đảo có ~m~ cây cầu được xây sắn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_i~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~
• ~D~ ~j~ có tác dụng xóa đi cầy cầu thứ ~j~ (nếu lúc này nó vẫn tồn tại) nối hai hòn đảo ~u_i~ và ~v_j~.

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input:

• Dòng thứ nhất gồm ~3~ số nguyên ~n,m,q~ ~(n,m,q \le 3*10^5)~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1,w_2,...,w_n~ ~(w_i \le 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_i~ và ~v_j~.
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~.

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Subtask

• Có ~30\%~ số test chứa ~n,m,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output 1

15
11
11
11
17
17
17
9

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một số nguyên dương ~k~. Hãy in ra đoạn con liên tiếp có tổng lớn thứ ~k~. (Có ~n*(n+1)/2~ đoạn con liên tiếp trong dãy).

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(1 \le k \le n*(n+1)/2)~.
• Dòng thứ 2 gồm ~n~ số nguyên miêu tả dãy ~a~. ~(-10^9 \le a_i \le 10^9)~.

Ouput

• In ra giá trị của đoạn con liên tiếp có tổng lớn thứ ~k~.

Sample Test

Input

4 3
1 -1 2 -2

Output

1

Giải thích: đoạn con ~[1,3], [3,3]~ là hai đoạn con có giá trị lớn nhất với tổng bằng ~2~. Tiếp đến là hai đoạn con ~[1,1], [2,3]~ có tổng bằng ~1~ có giá trị lớn thứ ~3~ và ~4~. Vậy đoạn con có giá trị lớn thứ ~k~ sẽ có giá trị bằng ~1~.

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%)