406797: GYM102558 D Перемещение чанков

D. Перемещение чанковограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

Один из кластеров хранилища состоит из $$$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 1
1
1 2 1 1

Выходные данные

1

Входные данные

1 2 1
1
2 1 1 1

Выходные данные

0

Входные данные

5 5 6
1 2 3 4 5
1 2 1 1
2 3 1 3
4 2 4 4
2 5 1 4
3 2 2 3
3 2 3 3

Выходные данные

1
0
1
0
0
1

Примечание

Рассмотрим третий пример. Изначально расположение чанков на серверах описывается массивом $$$[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]$$$.