You have at your disposal $$$k$$$ servers, which store information that can be represented as an array of $$$n$$$ elements. At the initial moment in time, all the information on all $$$k$$$ servers is identical, and it will be given to you in the form of an array $$$a$$$. Also, at certain times, requests are sent to the servers, and there are two types of requests:
You would like to create a system that will allow you to quickly process all these requests. But that's not all; you would also like to set up synchronization between all servers every $$$s$$$ seconds, meaning that every $$$s$$$ seconds, the servers exchange information and update so that there are no differences between the data of two different servers. Conflicts that arise during synchronization should be resolved automatically as follows: suppose there are different values at position $$$i$$$ on the servers, then during synchronization, the value that was updated later will be chosen for updating, i.e., if on server $$$x$$$ at position $$$i$$$ the value was changed at time $$$t_{1}$$$, and on server $$$y$$$ at position $$$i$$$ at time $$$t_{2}$$$, and $$$t_{1} \gt t_{2}$$$, then the value on server $$$x$$$ will be chosen.
Can you handle such a task?
The first line contains three integers $$$k, n$$$ ($$$1 \le k, n \le 10^{5}$$$) and $$$s$$$ ($$$1 \le s \le 10^{9}$$$) – the number of servers, the size of the data array on each server, and the synchronization period, respectively.
The second line contains $$$n$$$ integers $$$a_{i}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$) – the information stored on each server at the initial moment in time.
The third line contains one integer $$$q$$$ ($$$1 \le q \le 10^{6}$$$) – the number of requests.
The following $$$q$$$ lines contain requests, one per line. The requests are given in the following format:
For each request, in addition to the parameters described in the problem statement, the moment in time at which it arrives is also given. The parameters have restrictions ($$$1 \le time \le 10^{9}$$$), ($$$1 \le sid \le k$$$), ($$$1 \le pos \le n$$$), ($$$-10^{9} \le val \le 10^{9}$$$).
Note that if any request arrives at time $$$t$$$ and synchronization is supposed to occur at that moment ($$$t \bmod s = 0$$$), then synchronization of the servers occurs first, and only then is the request processed by the system.
Requests are given in increasing order of $$$time$$$.
Additional restriction: no two requests have the same $$$time$$$.
For each "Get" request, output the response that your system will provide.
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
