У Алисы и Боба есть доска из $$$n$$$ строк и $$$m$$$ столбцов. В каждой строке есть ровно одна фишка.

Алиса и Боб играют в следующую игру. Они выбирают два целых числа $$$l$$$ и $$$r$$$, такие, что $$$1 \le l \le r \le m$$$, и разрезают доску таким образом, что только столбцы с $$$l$$$ по $$$r$$$ (включительно) принадлежат доски. То есть все столбцы левее столбца $$$l$$$ и все столбцы правее столбца $$$r$$$ больше не являются частью доски.

После разрезания доски они начинают свою игру на оставшейся части доски (от столбца $$$l$$$ до столбца $$$r$$$). Они ходят по очереди, и первый игрок, который не может сделать ход, проигрывает. Первый ход делает Алиса, второй — Боб, третий — снова Алиса, и так далее. Во время своего хода игрок должен выбрать одну из фишек и сдвинуть ее на любое количество столбцов влево (то есть, если фишка была в столбце $$$i$$$, ее можно переместить в любой столбец $$$j < i$$$, а фишки в самом левом столбце двигать нельзя). Фишки не должны покидать выбранную часть доски.

У Алисы и Боба есть $$$q$$$ пар чисел $$$L_i$$$ и $$$R_i$$$. Для каждой такой пары они хотят определить, кто выиграет, если $$$l = L_i$$$ и $$$r = R_i$$$. Обратите внимание, что эти игры рассматриваются независимо (они не влияют на положение на доске в последующих играх), и оба игрока играют оптимально.