Xâu \(s\) được gọi là xâu con của xâu \(x\) nếu ta có thể nhận được \(s\) từ \(x\) bằng cách giữ nguyên hoặc xóa đi một số kí tự. Ví dụ, xâu bb là xâu con của xâu bab, nhưng xâu aa thì không phải là xâu con của xâu bab.

Cho hai xâu \(x\) và \(y\), tiến hành liệt kê (theo thứ tự từ điển) tất cả các xâu có độ dài \(n\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\).

Ví dụ, \(x =\) abab; \(y =\) abb và \(n = 2\), có hai xâu độ dài bằng \(2\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\) là: aa, ba.

Yêu cầu: Cho hai xâu \(x, y\) và \(m\) xâu \(s_{1}, s_{2}, \ldots, s_{m}\) có có cùng độ dài \(n\), hãy tìm thứ tự từ điển của các xâu \(s_{1}, s_{2}, \ldots, s_{m}\) khi liệt kê (theo thứ tự từ điển) tất cả các xâu có độ dài bằng \(n\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\).

Input

• Dòng đầu chứa ba số nguyên dương \(m, n, k\) \((m, n \leq 200, k \leq 10^{9})\).
• Dòng thứ hai chứa xâu \(x\).
• Dòng thứ ba chứa xâu \(y\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_{i}\).

Các xâu \(x, y, s_{1}, s_{2}, \ldots, s_{m}\) có độ dài không quá \(200\) và chỉ gồm các kí tự a đến z.

Output

• Gồm \(m\) dòng, gọi \(p_{i}\) là thứ tự từ điển của xâu \(s_{i}\) trong các xâu được xét, đưa ra số \(p_{i} \% k\) trên dòng \(i\) (phép toán \(\%\) là phép toán chia lấy dư). Nếu xâu \(s_{i}\) không phải xâu con của xâu \(x\) hoặc \(s_{i}\) là xâu con của xâu \(y\) thì ghi \(-1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Độ dài xâu \(x, y\) không vượt quá \(16\) và \(n = 1\).
• Subtask \(2\) (\(50\%\) số điểm): Độ dài xâu \(x, y\) không vượt quá \(16\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2 100
abab
abb
aa
ab
ba

1
-1
2