给定两个字符串 $s = s_1s_2 \dots s_n$ 和 $t = t_1t_2 \dots t_m$。现有若干次询问，对于每次询问，你需要求出满足以下条件的数对 $(x, y)$ 的数量：

• $l_s \le x \le r_s, l_t \le y \le r_t$
• 令 $p = s_x s_{x+1} \dots s_n t_1 t_2 \dots t_y$，且 $p$ 是 $s$ 或 $t$ 的子串。

输入格式

输入包含多组测试数据。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m, q \le 5 \times 10^5$)，分别表示字符串 $s$ 的长度、$t$ 的长度以及询问次数。

第二行包含一个长度为 $n$ 的字符串 $s$。第三行包含一个长度为 $m$ 的字符串 $t$。两个字符串均仅由小写英文字母组成。

接下来的 $q$ 行，每行包含四个整数 $l_s, r_s, l_t, r_t$ ($1 \le l_s \le r_s \le n, 1 \le l_t \le r_t \le m$)。

所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。所有测试数据中 $m$ 的总和不超过 $5 \times 10^5$。所有测试数据中 $q$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每次询问，输出一个整数表示答案。

样例

样例输入 1

3 3 3
aaa
aaa
1 3 1 3
1 1 2 2
3 3 1 1

样例输出 1

3
0
1