Cho dãy số nguyên dương \(A(a_1, a_2, \dots, a_n)\) và dãy các ký tự \(C(c_1, c_2, \dots, c_n)\). Người ta tạo ra xâu \(S\) độ dài \(l = a_1 + a_2 + \dots + a_n\) bằng cách ghép liên tiếp \(a_1\) ký tự \(c_1\), sau đó là \(a_2\) ký tự \(c_2, \dots\) cuối cùng là \(a_n\) ký tự \(c_n\).

Ví dụ: dãy \(A(2, 4, 3, 5)\), \(C(a, b, a, c)\) ta được xâu \(S = \text{aabbbbaaaccccc}\).

Ta cần xác định hàm tiền tố \(\pi: \{1, 2, \dots, l\} \to \mathbb{Z}\) như sau:
\(\pi(p) = \max\{i \mid 0 \le i < p; S[1 \dots i] = S[p - i + 1 \dots p]\}\) với \(S[u \dots v]\) là xâu con các ký tự liên tiếp từ vị trí \(u\) đến vị trí \(v\).

Yêu cầu: Cho dãy số \(A\), dãy ký tự \(C\) và \(m\) yêu cầu truy vấn \(p_i\). Với mỗi yêu cầu hãy xác định \(\pi(p_i)\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(n, m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^9, 1 \le i \le n\)). Các số ghi cách nhau bởi dấu cách.
• Dòng thứ ba chứa \(n\) ký tự \(c_1, c_2, \dots, c_n\) viết liên tiếp nhau (\(c_i \neq c_{i-1}\)).
• Dòng cuối cùng chứa \(m\) số nguyên dương \(p_1, p_2, \dots, p_m\) xác định các truy vấn.

Output

• Đưa ra các giá trị \(\pi(p_i)\) theo thứ tự các truy vấn. Các số ghi trên một dòng, cách nhau bởi một dấu cách.

Example

4 4
2 4 3 5
abab
2 5 9 11

1 0 2 4

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 100, l \le 10^4\).
• Subtask \(2\) (\(20\%\) số điểm): \(l \le 10^7, a_i \le 3000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, m \le 3000\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.