Bé Dino nhận được một mảnh giấy trên đó có ghi một đoạn ký tự chỉ có các ký tự latin in thường ~(a..z)~. Yêu cầu: Bạn hãy cho biết trong xâu ký tự Bé Dino nhận được có bao nhiêu lần xuất hiện đoạn ký tự ~virus~.

Input

• Gồm một xâu ký tự có độ dài ~\le 250~ ký tự.

Output

• Một số nguyên duy nhất là số lần xuất hiện xâu virus trong xâu ký tự đã cho.

Sample Input 1

hpvirushnviruss

Sample Output 1

2

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

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.

Hãy đếm số đoạn con liên tiếp ~[l,r]~ của dãy ~a~ sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay ~a_l + a_{l+1} + ... + a_r = r - l + 1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.

Output

• In ra số đoạn con thỏa mãn.

Điều kiện

• ~1 \le n \le 2*10^5~.
• ~0 \le a \le 9~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 2*10^5~.

Ví dụ

Input 1:

3
1 2 0

Output 1:

3

Input 2:

5
1 1 0 1 1 

Output 2:

6

Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.

Số tribonacci thứ ~i~ sẽ có công thức truy hồi như sau: ~f[i] = f[i-1] + f[i-2] + f[i-3]~ nếu ~i > 3~, ngược lại ~f[i] = i~ nếu ~i \le 3~.

Cho ~n~ số tribonacci đầu tiên và một số ~k~ (~k \le n~), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy ~n~ số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~n~ và số nguyên dương ~k~ ~(1 \le k \le n \le 10^5)~

Output

• Dòng đầu in ra số ~q~ là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra ~-1~.
• Dòng thứ hai in ra ~q~ chỉ số của dãy con tìm được.
• Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.

Subtask

• ~30\%~ số test có ~n \le 20~.
• ~40\%~ số test có ~n \le 2000~.
• ~30\%~ số test còn lại có ~n \le 10^5~.

Sample Test

Input:

5 4

Output:

2
2 4

Giải thích:

• ~5~ phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11

• Chọn ra phần tử thứ ~2~ và ~4~ có tổng bằng: ~2+6 = 8~ chia hết cho ~4~.

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