Cho một xâu s có độ dài n, chỉ gồm các chữ số từ ~0~ đến ~9~, và một số nguyên dương m.

Định nghĩa mảng a là một mảng số nguyên độ dài n, trong đó:

• a[i]=1 nếu giá trị số của xâu con s[0...i] chia hết cho m.
• a[i]=0 trong các trường hợp còn lại.

Hãy xây dựng và in ra mảng a.

Giải thích

Xâu s[0...i] là tiền tố của xâu ban đầu gồm các ký tự từ vị trí 0 đến i.

Ví dụ:

Nếu: s="998244353"

thì:

• s[0]="9"
• s[0...1]="99"

• s[0...2]="998"

• ...

Input

• Dòng đầu tiên chứa xâu s.
• Dòng thứ hai chứa số nguyên dương m.

Output

• In ra n số nguyên của mảng a.

Ví dụ

Ràng buộc

• ~1 \le n \le 10^5~
• ~|s|=n~
• ~s~ chỉ chứa các chữ số từ ~0~ đến ~9~
• ~1 \le m \le 10^9~