Bài tập

Cho một xâu \(s\) chỉ gồm các chữ cái thường Latin.
Mỗi ký tự trong xâu được đánh giá là tốt hoặc xấu.

Một xâu con liên tiếp của \(s\) được gọi là tốt nếu trong xâu con đó
có không quá \(K\) ký tự xấu.

Yêu cầu:
Hãy đếm số xâu con khác nhau của \(s\) mà là xâu con tốt.

**Lưu ý: hai xâu con là khác nhau khi nội dung của hai xâu là khác nhau, không quan trọng vị trí.

\InputFile

• Dòng đầu chứa xâu \(s\) \((|s| \le 1500)\).
• Dòng thứ hai chứa một xâu nhị phân \(b\) có độ dài \(26\),
  trong đó \(b_i = 1\) nếu ký tự thứ \(i\) trong bảng chữ cái là tốt,
  và \(b_i = 0\) nếu ký tự đó là xấu.
• Dòng thứ ba chứa số nguyên \(K\) \((0 \le K \le |s|)\).

\OutputFile
In ra một số nguyên duy nhất --- số lượng xâu con khác nhau của \(s\) mà là xâu con tốt.

Example

ababab
01000000000000000000000000
1

5

Cho \(n\) xâu \(S_1, S_2, \dots, S_n\).

Hãy tìm một xâu \(S\) có độ dài nhỏ nhất sao cho mọi \(S_1, S_2, \dots, S_n\) đều là xâu con liên tiếp của \(S\).
In ra độ dài của xâu \(S\) ngắn nhất đó.

\InputFile
Dòng đầu tiên gồm số nguyên \(n\).

\(n\) dòng tiếp theo, mỗi dòng gồm một xâu \(S_i\).

\OutputFile
In ra độ dài của xâu \(S\) ngắn nhất.

Điều kiện

• \(1 \le n \le 20\).
• \(1 \le |S_i| \le 100\).

Example

3
ab
bcc
da

5

Nhân dịp đầu năm mới, một cửa hàng đồ uống triển khai chương trình khuyến mãi đặc biệt dành cho khách hàng thân thiết. Nội dung của chương trình như sau: khi khách hàng mang đến cửa hàng \(10\) vỏ chai bia (cùng loại), họ sẽ được đổi lấy \(3\) chai bia mới miễn phí.

Anh Quân là một khách hàng đã mua ban đầu \(n\) chai bia. Sau khi uống hết, anh Quân muốn tận dụng chương trình khuyến mãi này để đổi vỏ chai lấy thêm bia. Anh Quân có thể tiếp tục uống và đổi vỏ chai mới nếu có, cho đến khi không thể đổi được nữa.

Yêu cầu: Hãy xác định tổng số chai bia tối đa mà anh Quân có thể uống được.

Input

Dữ liệu vào là một số nguyên dương \(n\) (\(1 \le n \le 10000\)) đại diện cho số chai bia anh Quân đã mua ban đầu.

Output

In ra một số nguyên duy nhất là tổng số chai bia tối đa mà anh Quân có thể uống được.

Example

16

19

10

13

Tý có \(A\) cái kẹo chanh, \(B\) cái kẹo dừa và muốn chia tất cả cho vài người bạn. Tý nhắm tính: nếu mỗi bạn nhận được số kẹo bằng nhau với mỗi loại thì sẽ có bao nhiêu cách để chia.

Ví dụ: Với \(A = 4, B = 12\) , có ba cách chia:

• Nếu chia cho một bạn thì bạn đó sẽ nhận \(4\) cái kẹo chanh và cái \(12\) kẹo dừa;
• Nếu chia cho hai bạn thì mỗi bạn sẽ nhận \(2\) cái kẹo chanh và cái kẹo \(6\) dừa;
• Và nếu chia cho bốn bạn thì mỗi bạn sẽ nhận \(1\) cái kẹo chanh và cái \(3\) kẹo dừa.

Yêu cầu: Hãy giúp Tý tìm và ghi ra tất cả các cách có thể chia hết số kẹo cho các bạn sao cho
mỗi bạn luôn nhận được số kẹo bằng nhau mỗi loại. Giả sử Tý có vô số bạn bè để chia kẹo

Input

Dữ liệu vào từ tập văn bản CAU3.INP gồm một dòng chứa hai số nguyên \(A, B\) cách nhau dấu cách (\(1 \leq A, B \leq 10^{17}\)).

Output

Ghi ra tập văn bản CAU3.OUT tương ứng với mỗi cách chia ghi ra ba số nguyên \(n, x, y\) cách nhau dấu cách. Số \(n\) là số bạn mà Tý có thể chia kẹo. Số \(x\) và \(y\) là số kẹo chanh và kẹo dừa mà mỗi bạn nhận được trong cách chia đó. Mỗi cách chia ghi ra đúng một lần và theo thứ tự tăng của \(n\).

Example

4 12

1 4 12
2 2 6
4 1 3

Scoring

• \(30\%\) số tests tương ứng \(30\%\) số điểm của bài có \(A, B \leq 10^7\);
• \(30\%\) số tests khác tương ứng \(30\%\) số điểm của bài có \(A, B \leq 10^{12}\);
• \(40\%\) số tests còn lại tương ứng \(40\%\) số điểm của bài không có ràng buộc gì thêm.