Trong một kỳ thi, số báo danh của thí sinh có định dạng như sau: CC-NNN.NN. Trong đó:

• Hai ký tự đầu tiên là chữ cái tiếng Anh in hoa từ 'A' đến 'Z';

• Ký tự thứ ba là ký tự '-';

• Tiếp theo là ba ký tự chữ số (từ '0' đến '9');

• Ký tự thứ bảy là ký tự '.';

• Cuối cùng là hai ký tự chữ số (từ '0' đến '9').

Do quá trình nhập liệu thủ công, số báo danh có thể bị sai định dạng. Cho một xâu mô tả một số báo danh cần kiểm tra. Các ký tự trong xâu được đánh số bắt đầu từ ~1~.

Yêu cầu: Hãy xác định số báo danh đó đúng định dạng hay không. Nếu số báo danh đúng định dạng thì in ra ~0~, ngược lại nếu số báo danh không đúng định dạng thì in ra vị trí ký tự đầu tiên bị sai định dạng.

Input

Một dòng duy nhất gồm xâu ký tự có độ dài không quá ~50~ là số báo danh cần kiểm tra.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

AC.123-45

Sample Output 1

3

Sample Input 2

AB-123

Sample Output 2

7

Sample Input 3

AB-123.45

Sample Output 3

0

Sample Input 4

AB-123.45.678

Sample Output 4

10

Cho một chuỗi ký tự mô tả công thức hóa học của một chất hữu cơ chỉ gồm ~3~ loại ký tự 'C', 'H', 'O' (tương ứng với các nguyên tố Carbon, Hydrogen, Oxygen) và các chữ số. Liền sau mỗi nguyên tố có thể là một số nguyên có giá trị không vượt quá ~10^{12}~ mô tả số lượng nguyên tử tương ứng với nguyên tố đó (nếu không có số nguyên liền sau mỗi nguyên tố thì có thể hiểu là số lượng nguyên tử tương ứng với nguyên tố đó bằng ~1~).

Ví dụ: Một chuỗi ký tự mô tả công thức hóa học như sau: C6H12O6, CH3OH, C2H5OH,...

Yêu cầu: Cho các giá trị nguyên tử khối của các nguyên tố như sau: ~C=12~, ~H=1~, ~O=16~. Hãy tính phân tử khối của chất hữu cơ được mô tả bởi chuỗi ký tự đã cho.

Input

Một dòng duy nhất gồm chuỗi ký tự có độ dài không vượt quá ~10^5~ mô tả công thức hóa học của một chất hữu cơ, chỉ gồm ~3~ loại ký tự 'C', 'H', 'O' và các chữ số.

Output

Một số nguyên dương duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

CH3OH

Sample Output 1

32

Sample Input 2

C6H12O6

Sample Output 2

180

Sample Input 3

C2H5OH

Sample Output 3

46

Notes

• Ví dụ 1: Phân tử khối của chất hữu cơ là: ~12 + 1 \times 3 + 16 + 1 = 32~.

• Ví dụ 2: Phân tử khối của chất hữu cơ là: ~12 \times 6 + 1 \times 12 + 16 \times 6 = 180~.

• Ví dụ 3: Phân tử khối của chất hữu cơ là: ~12 \times 2 + 1 \times 5 + 16 + 1 = 46~.

Cho dãy số gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ có giá trị thuộc tập hợp ~\{0, 1, 2, 3\}~.

Yêu cầu: Đếm số lượng các đoạn con gồm các số nguyên liên tiếp của dãy số sao cho:

• Gồm đúng ba loại giá trị;

• Số lần xuất hiện của các loại giá trị bằng nhau.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(N \le 10^6)~ là số lượng số trong dãy;

• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(0 \le A_i \le 3)~ mô tả dãy số.

Output

Một dòng duy nhất gồm một số nguyên là số đoạn con thoả mãn.

Scoring

Sample Input 1

11
0 1 2 1 2 0 3 1 0 3 1

Sample Output 1

9

Notes

• Có ~7~ đoạn con độ dài ~3~ thoả mãn là: ~[0, 1, 2]~, ~[1, 2, 0]~, ~[2, 0, 3]~, ~[0, 3, 1]~, ~[3, 1, 0]~, ~[1, 0, 3]~, ~[0, 3, 1]~.

• Có ~2~ đoạn con độ dài ~6~ thoả mãn là: ~[0, 1, 2, 1, 2, 0]~, ~[0, 3, 1, 0, 3, 1]~.

• Tổng có ~9~ đoạn con thỏa mãn.

Trong bảng chữ cái tiếng Anh, các ký tự nguyên âm là: 'a', 'e', 'o', 'u', 'i', các ký tự còn lại là phụ âm. Mỗi ký tự đều có một mã ASCII là một số nguyên dương, mã ASCII của ký tự 'a' là ~97~, mã ASCII của ký tự 'b' là ~98~, ..., mã ASCII của ký tự 'z' là ~122~.

Cho một xâu ký tự ~S~ chỉ gồm các chữ cái in thường trong bảng chữ cái tiếng Anh và một số nguyên ~K~. Xét một xâu con liên tiếp của ~S~: gọi ~X~ là tổng mã ASCII của các ký tự nguyên âm trong xâu con, gọi ~Y~ là tổng mã ASCII của các ký tự phụ âm trong xâu con.

Xâu con được coi là xâu đặc biệt nếu thỏa mãn:

• ~X > 0~;

• ~Y > 0~;

• ~0 \le X - Y \le K~;

• Tất cả các nguyên âm đều nằm ở một phía của xâu con. Ví dụ: "aexyz", "you", "aeiout".

Yêu cầu: Hãy đếm số lượng xâu con liên tiếp của xâu ~S~ là xâu đặc biệt.

Input

• Dòng đầu tiên gồm xâu ~S~ có độ dài không vượt quá ~10^6~;

• Dòng thứ hai gồm số nguyên ~K~ ~(0 \le K \le 10^6)~.

Output

Một số nguyên duy nhất là số lượng xâu con đặc biệt.

Scoring

Sample Input 1

erhdeu
4

Sample Output 1

1

Notes

Xâu con "de" có ~X=101~, ~Y=100~; ~0 \le X - Y = 1 \le K~. Thỏa mãn là xâu đặc biệt.

Trong một trò chơi tìm kho báu, bản đồ được mã hóa thành một bảng hình chữ nhật có ~M~ hàng và ~N~ cột. Các hàng được đánh số từ ~1~ đến ~M~, các cột được đánh số từ ~1~ đến ~N~, ô ở hàng ~i~, cột ~j~ trên bảng gọi là ô ~(i, j)~ có giá trị là một trong bốn loại ký tự:

• '0': mô tả ô đất liền;

• '1': mô tả ô biển;

• '@': mô tả ô vị trí xuất phát của nhân vật (luôn ở trên đất liền);

• '#': mô tả ô chứa kho báu (luôn ở trên đất liền).

Nhân vật không biết bơi nên sẽ không thể đi vào ô biển và luôn luôn đứng ở ô đất liền. Nhân vật có thể di chuyển trên bản đồ theo các cách sau:

• Đi bộ tự do sang các ô đất liền chung cạnh.

• Nhảy qua biển theo một trong ~4~ hướng Đông, Tây, Nam, Bắc đến ô đất liền đầu tiên trên hướng nhảy đó.

Yêu cầu: Nhân vật xuất phát ở ô có ký tự '@', và muốn di chuyển đến ô có ký tự '#' chứa kho báu. Vì mỗi lần nhảy qua biển tiêu hao nhiều năng lượng, hãy giúp nhân vật tìm số lần nhảy nhỏ nhất để có thể di chuyển đến ô có kho báu.

Input

• Dòng đầu tiên gồm hai số nguyên ~M, N~ ~(1 \le M, N \le 10^3)~;

• ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự mô tả bản đồ.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

4 8
@0011011
11111011
1001101#
11111011

Sample Output 1

2

Sample Input 2

1 9
@1011101#

Sample Output 2

3

Notes

• Ví dụ 1: Một cách di chuyển có số lần nhảy nhỏ nhất là ~2~ như sau:

  • Xuất phát từ ô ~(1,1)~, đi bộ sang ô ~(1,2)~, rồi đi bộ sang ô ~(1,3)~.

  • Nhảy từ ô ~(1,3)~ sang ô ~(1,6)~. Đi bộ từ ô ~(1,6)~ sang ô ~(2,6)~, rồi đi bộ sang ô ~(3,6)~.

  • Nhảy từ ô ~(3,6)~ sang ô ~(3,8)~ chứa kho báu.

• Ví dụ 2: Cách di chuyển có số lần nhảy nhỏ nhất là ~3~ như sau: Xuất phát từ ô ~(1,1)~, nhảy sang ô ~(1, 3)~, rồi nhảy sang ô ~(1,7)~, rồi nhảy sang ô ~(1,9)~ chứa kho báu.

Hai số nguyên dương ~a, b~ được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng là 1. Cho hai số nguyên dương ~N~ và ~Q~.

Yêu cầu: Thực hiện ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L, R~. Hãy đếm số lượng số nguyên tố cùng nhau với ~N~ trong đoạn ~[L, R]~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, Q~ ~(1 \le N \le 10^{11}; 1 \le Q \le 3 \times 10^4)~;

• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L, R~ ~(1 \le L \le R \le 10^{15})~ mô tả truy vấn.

Output

Gồm ~Q~ dòng, mỗi dòng in ra kết quả của truy vấn tương ứng.

Scoring

Sample Input 1

10 2
1 5
5 10

Sample Output 1

2
2

Notes

• Truy vấn 1: trong đoạn ~[1,5]~ có 2 số nguyên tố cùng nhau với 10 là 1 và 3.

• Truy vấn 2: trong đoạn ~[5,10]~ có 2 số nguyên tố cùng nhau với 10 là 7 và 9.

Có ~N~ búp bê Matryoshka rỗng ruột được đánh số từ 1 đến ~N~. Búp bê thứ ~i~ ~(1 \le i \le N)~ có đường kính ~D_i~, chiều cao ~H_i~ và nó có thể đặt vào bên trong búp bê khác nếu cả đường kính và chiều cao đều nhỏ hơn. Các búp bê đặt được vào bên trong nhau được gọi là một nhóm.

Có ~Q~ truy vấn, mỗi truy vấn cho hai số nguyên dương ~A, B~ với ý nghĩa như sau:

• Chỉ xét những búp bê có kích thước đường kính ~D~ và chiều cao ~H~ thỏa mãn: ~D \ge A~ và ~H \le B~.

• Tìm cách đặt các búp bê vào bên trong nhau sao cho số nhóm búp bê tạo thành nhỏ nhất.

Yêu cầu: Với mỗi truy vấn, hãy tính số nhóm búp bê nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~ là số lượng búp bê;

• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~D_i~ và ~H_i~ mô tả đường kính và chiều cao của búp bê thứ ~i~ ~(1 \le i \le N; 1 \le D_i, H_i \le 10^9)~;

• Dòng tiếp theo gồm số nguyên ~Q~ ~(1 \le Q \le 2 \times 10^5)~ là số lượng truy vấn;

• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~A, B~ ~(1 \le A, B \le 10^9)~ mô tả truy vấn.

Output

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

Scoring

Sample Input 1

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

Sample Output 1

2

Notes

• Xét các búp bê có ~D \ge 3~ và ~H \le 5~, đó là búp bê có thứ tự 1, 3, 4, 6 có kích thước tương ứng: ~(4, 1), (6, 4), (6, 1), (5, 2)~.

• Một cách đặt các búp bê vào bên trong nhau sao cho số nhóm tạo thành nhỏ nhất là:

  • Nhóm 1: Gồm ba búp bê đặt bên trong nhau theo thứ tự là ~(6, 4), (5, 2), (4, 1)~;

  • Nhóm 2: Gồm duy nhất một búp bê ~(6, 1)~;

  Vậy kết quả là 2.

An có ~N~ chiếc kẹo dự định chia cho ~M~ bạn được đánh số từ 1 đến ~M~. Bạn nào cũng sẽ nhận được tối thiểu 1 chiếc kẹo. An biết rằng, bạn thứ ~i~ ~(1 \le i \le M)~ có mức độ thích đồ ngọt là ~D_i~. Gọi ~S_i~ là số lượng bạn nhận được nhiều kẹo hơn bạn thứ ~i~. Khi đó, độ vui vẻ của bạn thứ ~i~ sẽ bị giảm đi ~D_i \times S_i~.

Yêu cầu: Cho ~T~ truy vấn ~N_1, N_2, \dots, N_T~ tương ứng với số kẹo mà An có. Với mỗi truy vấn, hãy giúp An tìm cách chia kẹo để tổng độ vui vẻ bị giảm đi của ~M~ bạn là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~M, T~ ~(1 \le M \le 100; 1 \le T \le 10^5)~ là số lượng bạn của An và số truy vấn;
• Dòng thứ hai gồm ~M~ số nguyên ~D_1, D_2, \dots, D_M~ ~(0 \le D_i \le 10^5; 1 \le i \le M)~ là mức độ thích đồ ngọt của ~M~ bạn;
• Dòng thứ ba gồm ~T~ số nguyên mô tả các truy vấn tương ứng là số kẹo mà An có: ~N_1, N_2, \dots, N_T~ ~(1 \le i \le T; M \le N_i \le 10^9)~.

Output

Gồm một dòng chứa ~T~ số, số thứ ~i~ ~(1 \le i \le T)~ là tổng độ vui vẻ bị giảm đi nhỏ nhất trong trường hợp An có ~N_i~ chiếc kẹo.

Scoring

Sample Input 1

3 2
100 200 300
5 6

Sample Output 1

200 0

Notes

• Truy vấn 1: có thể chia số kẹo như sau: 1, 2, 2.
• Truy vấn 2: có thể chia đều số kẹo cho mỗi bạn là 2, 2, 2.

Cho một cây gồm ~N~ đỉnh và ~N-1~ cạnh có trọng số. Các cạnh được đánh số từ 1 đến ~N-1~, cạnh thứ ~i~ nối cặp đỉnh ~(u, v)~ có trọng số ~c~.

Chi phí đường đi giữa hai đỉnh ~(u, v)~ là tổng trọng số các cạnh trên đường đi từ ~u~ đến ~v~ (~u \ne v~). Nếu không tồn tại đường đi từ ~u~ đến ~v~ thì chi phí đường đi giữa cặp đỉnh ~(u, v)~ là 0.

Một cách xóa cạnh được mô tả như sau:

• Chọn hai số nguyên dương ~L, R~ thoả mãn ~1 \le L \le R \le N-1~;

• Xóa tất cả các cạnh được đánh số từ ~L~ đến ~R~.

Cho trước một số nguyên dương ~K~. Một cách xóa cạnh được gọi là "đẹp" nếu mọi chi phí đường đi giữa cặp đỉnh bất kỳ không vượt quá ~K~. Hai cách xóa cạnh được coi là khác nhau khi có một cạnh trong cách xóa này không có trong cách xóa kia.

Yêu cầu: Đếm số lượng cách xóa cạnh được gọi là "đẹp".

Input

Dòng đầu tiên gồm hai số nguyên ~N, K~ (~1 \le N \le 10^5~; ~1 \le K \le 10^9~).

~N-1~ dòng sau, mỗi dòng gồm ba số nguyên ~u, v, c~ mô tả cạnh nối đỉnh ~u~ và đỉnh ~v~, có trọng số là ~c~ (~1 \le u, v \le N~; ~1 \le c \le 10^6~).

Output

Một số nguyên duy nhất là số lượng cách xóa cạnh được gọi là "đẹp".

Scoring

Sample Input 1

6 12
1 2 3
1 4 5
2 3 6
2 5 4
3 6 9

Sample Output 1

9

Notes

Có 9 cách xóa cạnh "đẹp" được mô tả chi tiết:

• ~L=1, R=1~: Xóa cạnh 1. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 2 đến đỉnh 6 là 15 lớn hơn ~K=12~.

• ~L=1, R=2~: Xóa cạnh 1, 2. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 2 đến đỉnh 6 là 15 lớn hơn ~K=12~.

• ~L=1, R=3~: Xóa cạnh 1, 2, 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=1, R=4~: Xóa cạnh 1, 2, 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=1, R=5~: Xóa cạnh 1, 2, 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì không tồn tại đường đi giữa mọi cặp đỉnh.

• ~L=2, R=2~: Xóa cạnh 2. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 5 đến đỉnh 6 là 19 lớn hơn ~K=12~.

• ~L=2, R=3~: Xóa cạnh 2, 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=2, R=4~: Xóa cạnh 2, 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=2, R=5~: Xóa cạnh 2, 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 1 đến đỉnh 2 là 3 không vượt quá ~K=12~.

• ~L=3, R=3~: Xóa cạnh 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 4 đến đỉnh 5 là 12 không vượt quá ~K=12~.

• ~L=3, R=4~: Xóa cạnh 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=3, R=5~: Xóa cạnh 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 2 đến đỉnh 4 là 8 không vượt quá ~K=12~.

• ~L=4, R=4~: Xóa cạnh 4. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 4 đến đỉnh 6 là 23 lớn hơn ~K=12~.

• ~L=4, R=5~: Xóa cạnh 4, 5. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 3 đến đỉnh 4 là 14 lớn hơn ~K=12~.

• ~L=5, R=5~: Xóa cạnh 5. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 3 đến đỉnh 4 là 14 lớn hơn ~K=12~.