В вашем распоряжении $$$k$$$ серверов, на этих серверах хранится информация, ее можно представить в виде массива из $$$n$$$ элементов. В изначальный момент времени вся информация на всех $$$k$$$ серверах одинаковая, вам она будет дана в виде массива $$$a$$$. Также в некоторые моменты времени к серверам поступают запросы, запросы бывают двух типов:
Вы бы хотели создать такую систему, которая позволит быстро обрабатывать все эти запросы. Но это еще не все, также вы бы хотели настроить синхронизацию между всеми серверами раз в $$$s$$$ секунд, то есть каждые $$$s$$$ секунд серверы обмениваются информацией и обновляются так, что между данными двух различных серверов нет различий. Конфликты, которые возникают при синхронизации, должны устраняться в автоматическом режиме следующим образом: допустим на серверах в позиции $$$i$$$ находятся разные значения, тогда при синхронизации для обновления будет выбрано то значение, которое было позже обновлено, то есть если на сервере $$$x$$$ в $$$i$$$-й позиции значение было изменено в момент времени $$$t_{1}$$$, а на сервере $$$y$$$ в $$$i$$$-й позиции в момент $$$t_{2}$$$ и при этом $$$t_{1} \gt t_{2}$$$, то будет выбрано значение на сервере $$$x$$$.
Сможете ли вы справиться с такой задачей?
Первая строка содержит три целых числа $$$k, n$$$ ($$$1 \le k, n \le 10^{5}$$$) и $$$s$$$ ($$$1 \le s \le 10^{9}$$$) – количество серверов, размер массива данных на каждом сервере и период синхронизации соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_{i}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$) – информацию, которая хранится на каждом сервере в нулевой момент времени.
Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^{6}$$$) – количество запросов.
Следующие $$$q$$$ строк содержат запросы, по одному на каждой строке. Запросы даны в следующем формате:
Для каждого запроса, помимо параметров, описанных в условии, также дан момент времени, в который он приходит. Параметры имеют ограничения ($$$1 \le time \le 10^{9}$$$), ($$$1 \le sid \le k$$$), ($$$1 \le pos \le n$$$), ($$$-10^{9} \le val \le 10^{9}$$$).
Обратите внимание, что если какой-либо запрос приходит в момент времени $$$t$$$ и при этом в этот момент должна произойти синхронизация ($$$t \bmod s = 0$$$), то сначала происходит синхронизация серверов, а потом уже системой обрабатывается этот запрос.
Запросы даны в порядке увеличения $$$time$$$.
Гарантируется, что никакие два запроса не имеют одинаковый $$$time$$$.
Для каждого запроса типа «Get» выведите ответ, который даст ваша система.
2 5 10 3 2 2 4 4 5 4 Get 2 3 7 Set 2 3 1 8 Get 1 3 9 Get 2 3 100 Get 1 3
2 2 1 1
5 5 60 0 0 0 0 0 8 1 Get 1 5 2 Set 2 2 7 7 Set 5 2 1 59 Get 2 2 60 Get 2 2 61 Get 3 2 69 Set 4 1 9 120 Get 1 1
0 7 1 1 9
