== include(page="template/taskheader" task_id="Aby") ==
 

Se spune ca odata, demult , in vechea tara Lapestina exista un castel magic.
De curand maleficul Rainbowdash din Rasiel a rapit-o pe printesa Lolita, iar eroul nostru, Abu, este pregatit sa faca orice

Abu a obtinut in calatoriile lui T harti dintre care una sigura corespunde castelului, dar nefiind sigur care dintre ele , el va roaga sa-i spuneti
pentru fiecare daca este posibil sa-si salveze printesa, presupunand ca maleficul Rainbowdash nu-si greseste miscarile.

 
h2. Date de intrare
 
Fişierul de intrare $x.in$ va contine pe prima linie $3$ numere naturale $N$, $M$, $Q$. $N$ este lungimea primului sir, $M$ este lungimea celui de al doilea sir iar $Q$ este numarul de intrebari. A doua linie contine un sir de $N$ caractere ce reprezinta primul sir. A treia linie contine un sir de $M$ caractere ce reprezinta cel de al doilea sir. Pe urmatoarele $Q$ linii sunt cele $Q$ intrebari de forma $(x, y)$.
 
h2. Date de ieşire
 
Fişierul de ieşire $x.out$ va contine $Q$ linii. Pe linia $i$ trebuie sa afisati raspunsul la intrebarea $i$.
 
h2. Restricţii
 
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 1.000.000$
* $1 ≤ Q ≤ 500.000$
 
h2. Exemplu
 
table(example). |_. x.in |_. x.out |
| 5 4 1
  badab
  abac
  3 3
| 2
|