Given a string $s[1, n]$, each character $i$ is assigned two weights: a left weight $wl_i$ and a right weight $wr_i$.

The left weight $vl(s[l, r])$ of a substring $s[l, r]$ is defined as the sum of the left weights $wl$ of all its matching left endpoints in the original string. The right weight $vr(s[l, r])$ is defined as the sum of the right weights $wr$ of all its matching right endpoints in the original string. Here, all matches of $t$ in $s$ are defined as $\forall 1 \leq i \leq j \leq n, s[i, j]=t$, and we call such $i$ and $j$ the left and right endpoints of a match, respectively.

The "repetition degree" of a substring $s[l, r]$ is defined as the product of its left weight and right weight, i.e., $w(s[l, r])=vl(s[l, r]) \cdot vr(s[l, r])$.

There are $q$ queries, each given by $l_1, r_1, l_2, r_2$. Let $S=\left\{(l, r) \mid r-l \geq \max \left\{r_1-l_1, r_2-l_2\right\}, s\left[l, l+r_1-l_1\right]=s\left[l_1, r_1\right], s\left[r-r_2+l_2, r\right]=s\left[l_2, r_2\right]\right\}$, which is the set of all pairs $(l, r)$ such that $s[l_1, r_1]$ is a prefix of $s[l, r]$ and $s[l_2, r_2]$ is a suffix of $s[l, r]$. Calculate $\sum_{(l, r) \in S} w(s[l, r])$.

Since the answer can be very large, you only need to output the result modulo $2^{64}$.

Input

The first line contains two positive integers $n$ and $q$, representing the length of the string and the number of queries.

The second line contains a string $s$ consisting of lowercase letters.

The third line contains $n$ integers $wl_i$, representing the left weights.

The fourth line contains $n$ integers $wr_i$, representing the right weights.

The next $q$ lines each contain four integers $l_1, r_1, l_2, r_2$, representing a query.

Output

Output $q$ lines, where the $i$-th line contains the answer to the $i$-th query modulo $2^{64}$.

Examples

Input 1

6 5
ababcc
1 1 1 1 1 1
1 1 1 1 1 1
1 1 5 5
3 4 1 2
1 1 2 2
1 2 6 6
5 5 1 2

Output 1

4
9
9
4
0

Constraints

It is guaranteed that $1 \leq n, q \leq 10^5$, $0 \leq wl_i, wr_i < 2^{64}$, $1 \leq l_1 \leq r_1 \leq n$, $1 \leq l_2 \leq r_2 \leq n$, and $s$ consists only of lowercase letters.

• Subtask 1 (7 pts): $n, q \leq 500$.
• Subtask 2 (15 pts): $n, q \leq 5000$.
• Subtask 3 (12 pts): $n \leq 5000$.
• Subtask 4 (6 pts): $l_1=1$, and for any $2 \leq i \leq n$, $s_1 \neq s_i$.
• Subtask 5 (16 pts): $s[l_1, r_1]$ appears at most 5 times in $s$.
• Subtask 6 (21 pts): $n, q \leq 5 \times 10^4$.
• Subtask 7 (23 pts): No additional restrictions.