In the Shapez Factory, there is a tool called a "rotator." Using the rotator once allows you to cyclically shift a substring of length exactly 3 in a binary string, i.e., replacing $xyz$ with $yzx$ or $zxy$.

Given two binary strings $s$ and $t$ of length $n$, there are $q$ queries. Each query provides $l$ and $r$, and you must find the minimum number of times the rotator must be used to transform $s[l, r]$ into $t[l, r]$.

Input

Read the data from standard input.

The first line contains two positive integers $n$ and $q$, representing the length of the strings $s, t$ and the number of queries, respectively. The second line contains a binary string $s$ of length $n$. The third line contains a binary string $t$ of length $n$. The $i$-th line of the next $q$ lines ($1 \le i \le q$) contains two positive integers $l$ and $r$, representing the $i$-th query.

Output

Output to standard output.

For each query, output a single integer representing the minimum number of rotator operations required. Specifically, if it is impossible to transform $s[l, r]$ into $t[l, r]$ under any circumstances, output $-1$.

Examples

Input 1

10 5
1010111000
1111000001
1 6
3 5
4 5
1 10
8 9

Output 1

3
1
-1
5
0

Note

For the first query, one possible sequence of operations is: 1. Select substring $[4, 6]$, replace $011$ with $110$, resulting in $101110$; 2. Select substring $[2, 4]$, replace $011$ with $110$, resulting in $111010$; 3. Select substring $[4, 6]$, replace $010$ with $100$, resulting in $111100$.

Subtasks

For all test data, it is guaranteed that: $1 \le n, q \le 5 \times 10^5$; For all $1 \le i \le n$, $s_i, t_i \in \{0, 1\}$; * $1 \le l \le r \le n$.

Special Property A: For all $1 \le i \le \lfloor \frac{n+1}{2} \rfloor$, $s_{2i-1} = t_{2i-1} = 0$.