Wstęp do programowania w C++

Bajtar gra w grę platformową na swoim nowym komputerze. Plansza do gry składa się z n różnych pod sobą platform, po których może poruszać się postać gracza. Każda platforma ma długość X, tak więc pozycja postaci może być oznaczana za pomocą pary liczb (i, x), gdzie i to numer platformy (liczac od góry, a x to odciełosć od lewego krańca platformy (1 ≤ i ≤ n, 1 ≤ x ≤ X). Postać gracza startuje z lewego krańca pewnej platformy i musi dojsć do prawego krańca dowolnej platformy. Postać może poruszać się tylko w prawo.

Zebu nie było jednak tak prosto, to w niektórych miejscach na platformach znajdują się dziury, które utrudniają graczowi poruszanie się. Postać może je przeskakiwać albo unikać spadania/wskakiwania na platformy znajdujące się niżej/wyżej. Nigdzie na planszy nie ma dwóch dziur bezposrednio pod sobą, ani bezposrednio obok siebie.

Formalnie, jeśli postać znajduje się na pozycji (i, x), to możliwe ruchy gracza wygadaają następująco:

• Klawiszem F można przejść na pozycję (i, x + 1), jeśli nie znajduje się w niej dziura.
• Klawiszem F można spaść na pozycję (i + 1, x + 1), jeśli i ≠ n oraz na pozycji (i + 1) jest dziura.
• Klawiszem A można przeskoczyć na pozycję (i, x + 2), jeśli na pozycji (i, x + 1) jest dziura.
• Klawiszem B można wskoczyć na pozycję (i - 1, x + 1), jeśli i ≠ 1 oraz na pozycji (i - 1, x) jest dziura.

Znając początkowe położenie gracza obliczyć ile minimalnie skoków (czyli naciśnięć klawiszów A i B) potrzebuja, by dotrzeć do prawego krańca dowolnej platformy.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite n, X oraz z (1 ≤ n ≤ 100 000, 1 ≤ X ≤ 10⁹, 1 ≤ z ≤ 100 000) oznaczające liczbę i długość platform oraz liczbę zapytań.

W kolejnych n wierszach są opisane platformy; i-ty z nich zawiera nieujemną liczbę całkowitą k_i oznaczającą liczbę dziur na i-tej platformie, po których znajdują się rosnąco ciąg k_i liczb całkowitych oznaczających odciełości tych dziur od lewego końca platformy. Na żadnej platformie dziury nie znajdują się obok siebie, a na żadnej następującej po sobie platformach nie istnieje dziura majaąca te sama odciełość od lewego końca swojej platformy. Sumaryczna liczba dziur jest nie większa niż 2 000 000.

W kolejnych z wierszach znajdują się zapytania; i-ty z nich zawiera liczbę całkowitą p_i (1 ≤ p_i ≤ n).

Wyjście

Twój program powinien wypisać na wyjście z wierszy; j-ty z nich powinien zawierać liczbę całkowitą, będącą odpowiedzią na pytanie: ile minimalnie naciśnięć przycisków A i B potrzeba, żeby dojść z pozycji (pj , 1) na pozycję, której druga współrzędna to X.

Dla danych wejściowych:
3 9 3
1 6
2 3 8
2 5 7
3
2
1
poprawnym wynikiem jest:
1
1
0