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\ast {10}^5$.
• $0\le a\le 9$.

Subtask

• $50\mathrm{\%}$ số điểm: $n\le 1000$.
• $50\mathrm{\%}$ số điểm: $n\le 2\ast {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\mathrm{\%}$ số test có $n\le 20$.
• $40\mathrm{\%}$ số test có $n\le 2000$.
• $30\mathrm{\%}$ 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\mathrm{\%})$
• 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\mathrm{\%})$.

Sample Test

Input

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

Output

5
8
30