Everyone knows that Bayview's Computer Club owns a sick gaming PC with very sick RGB lights. The colours of these RGB lights can be represented by a sequence $A$ of length $N$. $A_i$ is R if the $i^{\text{th}}$ light is red, G if it is green, and B if it is blue.

For some reason, the computer club execs have decided that the current sequence of lights is ugly, and want to change the colours to match the sequence $B$.

Luckily, each of the lights can be toggled with a special remote control. When a light is toggled:

• If the light was red, it becomes green.
• If the light was green, it becomes blue.
• If the light was blue, it becomes red.

Not so luckily, this special remote has malfunctioned, and can only toggle seemingly random contiguous intervals of lights. The computer club execs use the remote $Q$ times, where during the $j^{\text{th}}$ use, all the lights in the interval $[l_j,r_j]$ are toggled. Please find the earliest time where the sequence of RGB lights equals $B$, or determine if this never occurs.

Constraints

$1\le N,Q\le {10}^6$

$1\le l_j\le r_j\le N$

Input Specification

The first line contains a single integer, $N$.

The second line contains $N$ letters, the sequence $A$. Each letter is either R, G, or B.

The third line contains $N$ letters, the sequence $B$. Each letter is either R, G, or B.

The fourth line contains a single integer, $Q$.

The next $Q$ lines contain two integers each, $l_j$ and $r_j$.

Output Specification

Output a single integer, the minimal value of $t$ such that after applying the first $t$ queries, the sequence of RGB lights equals $B$. If this never occurs, output -1. If the sequence of lights equals $B$ before any queries, output 0.

Sample Input 1

3
RRR
BBG
3
1 3
1 2
3 3

Sample Output 1

2

Explanation for Sample Output 1

After the remote is used for the first time, the sequence of lights becomes GGG.

After the second time, it becomes BBG, which matches the target sequence.

Sample Input 2

2
RG
BG
2
2 2
1 2

Sample Output 2

-1