5. Перемещение чанков

Хранение данных в распределённом хранилище является крайне сложной задачей, однако инженеры Яндекса успешно с ней справляются.

Один из кластеров хранилища состоит из $m$ серверов, на которых хранятся данные, разбитые на $n$ чанков. Для дефрагментации кластера и возможности отключения старых серверов чанки периодически приходится перемещать между серверами. Перемещение чанков по одному неэффективно, поэтому чанки перемещают группами. Запрос на перемещение чанков описывается четырьмя числами $a, b, l, r$ и обозначает заказ на перемещение всех чанков с номерами от $l$ до $r$ включительно с сервера с номером $a$ на сервер с номером $b$. После перемещения соотвествующие чанки с сервера с номером $a$ стираются. Таким образом, каждый чанк находится всегда ровно на одном сервере.

При построении распределённых систем очень важно избегать возможности конфликта изменений на кластере. Перед выполнением каждого из запросов необходимо убедиться, что все чанки, участвующие в запросе, находятся на ожидаемом сервере. Иными словами, перед выполнением запроса, описываемого параметрами $a, b, l, r$, необходимо убедиться, что все чанки с номерами от $l$ до $r$ включительно, расположены на сервере с номером $a$. В случае, если это неверно, запрос на перемещение чанков отменяется, и система переходит к обработке следующего запроса. Если же это верно, то запрос осуществляется и все чанки от $l$ до $r$ включительно перемещаются с сервера $a$ на сервер $b$.

По заданому начальному состоянию кластера и списку запросов перемещения чанков определите, какие запросы будут выполнены.

В первой строке заданы три целых числа $n, m$ и $q$ ($1 \leq n, q \leq 100\,000, 2 \leq m \leq 100\,000$) — количество чанков на кластере, количество серверов, на которых располагаются чанки, и количество запросов, соответсвенно.

Во второй строке содержатся $n$ чисел $p_i$ ($1 \leq p_i \leq m$), $i$-е из которых обозначает номер сервера, на котором изначально располагается чанк с номером $i$.

В следующих $q$ строках содежатся описания запросов перемещения чанков в хронологическом порядке.

Каждый запрос описывается четвёркой чисел $a_i, b_i, l_i, r_i$ ($1 \leq a_i, b_i \leq m, a_i \neq b_i, 1 \leq l_i \leq r_i \leq n$) и обозначает заказ на перемещение чанков с номерами с $l_i$ по $r_i$ (включительно) с сервера $a_i$ на сервер $b_i$.

Выведите $q$ строк. В строке с номером $i$ выведите $1$, если запрос с номером $i$ будет выполнен, и $0$ иначе.

Рассмотрим третий пример. Изначально, расположение чанков на серверах описывается массивом $[1, 2, 3, 4, 5]$.

В первом запросе требуется переместить чанк с номером $1$ с сервера $1$ на сервер $2$. Чанк с номером $1$ находится на сервере $1$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах описывается массивом $[2, 2, 3, 4, 5]$.

Во втором запросе требуется переместить чанки $1, 2$ и $3$ с сервера $2$ на сервер $3$. Чанк $3$ расположен не на сервере $2$, а на сервере $3$, поэтому операция не будет выполнена. Расположение чанков на серверах останется прежним.

В третьем запросе требуется переместить чанк $4$ с сервера $4$ на сервер $2$. Чанк $4$ находится на сервере $4$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах будет описываться массивом $[2, 2, 3, 2, 5]$.

В четвёртом запросе требуется переместить чанки $1, 2, 3$ и $4$ с сервера $2$ на сервер $5$. Так как чанк $3$ расположен на сервере $3$, а не на сервере $2$, запрос не будет выполнен и расположение чанков останется прежним.

В пятом запросе требуется переместить чанки $2$ и $3$ с сервера $3$ на сервер $2$, но чанк $2$ расположен на сервере $2$, поэтому запрос не будет выполнен, и расположение чанков останется прежним.

В шестом запросе требуется переместить чанк $3$ с сервера $3$ на сервер $2$. Чанк с номером $3$ находится на сервере $3$, поэтому перемещение будет произведено, и расположение чанков станет описываться массивом $[2, 2, 2, 2, 5]$.