Đề bài

Với một số nguyên $n$ ($1 \le n$), xâu ký tự được tạo thành bằng cách xếp xen kẽ $n+1$ chữ 'I' và $n$ chữ 'O' bắt đầu bằng 'I' được gọi là $P_n$. Ở đây, 'I' và 'O' là các chữ cái tiếng Anh in hoa.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI (có $n$ chữ 'O')

Hình 1-1: Xâu $P_n$ ứng với số nguyên $n$ ($1 \le n$)

Cho số nguyên $n$ và một xâu $s$ chỉ gồm các ký tự 'I' và 'O', hãy viết chương trình in ra số vị trí trong xâu $s$ có chứa xâu $P_n$.

Dữ liệu vào

Dữ liệu vào gồm $3$ dòng: - Dòng thứ $1$ chứa số nguyên $n$ ($1 \le n \le 1000000$). - Dòng thứ $2$ chứa số nguyên $m$ ($1 \le m \le 1000000$), trong đó $m$ biểu thị số ký tự của xâu $s$. - Dòng thứ $3$ chứa xâu $s$ chỉ gồm các ký tự 'I' và 'O'.

Trong mọi dữ liệu chấm, $2n + 1 \le m$ luôn thỏa mãn. Ngoài ra, đối với $50\%$ số điểm, $n \le 100$ và $m \le 10000$ được thỏa mãn.

Kết quả

In ra $1$ dòng duy nhất chứa một số nguyên biểu thị số vị trí trong xâu $s$ có chứa xâu $P_n$. Nếu $P_n$ không xuất hiện trong $s$, hãy in ra số nguyên $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Giải thích ví dụ

Khi số nguyên $n$ là $1$ và xâu $s$ là OOIOIOIOIIOII, xâu $P_1$ tức là IOI xuất hiện tại $4$ vị trí như Hình 1-2 dưới đây, nên số nguyên cần in ra là $4$.

OOIOIOIOIIOII
  ^^^
    ^^^
      ^^^
         ^^^

Hình 1-2: Trong Ví dụ 1, xâu $P_1$ xuất hiện tại $4$ vị trí

Khi số nguyên $n$ là $2$ và xâu $s$ là OOIOIOIOIIOII, xâu $P_2$ tức là IOIOI xuất hiện tại $2$ vị trí như Hình 1-3 dưới đây, nên số nguyên cần in ra là $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Hình 1-3: Trong Ví dụ 2, xâu $P_2$ xuất hiện tại $2$ vị trí