You are the creator of a famous programming contest platform and have recently suffered a DDoS attack. Faced with this problem, you have decided to implement an anti-DDoS system on your platform to be able to ignore requests from malicious IPs before they cause problems. In a few hours, an important contest is scheduled to start, which has taken a long time to prepare and people from all over the world have been waiting for months, but the platform is still in danger! As a great programmer, you have announced that before the start of the contest, the anti-DDoS system will be up and running and the contest will continue. You must implement it on time!
A byte consists of 8 digits in binary that encode a number between 0 and 255. In current computers, they function as the minimum unit of information, as the computer's memory works with bytes.
An IP consists of a string formed by four numbers representable in a single byte (that is, numbers between 0 and 255, without leading zeros) separated by dots (Examples: "192.168.1.1", "127.0.0.1"). These are used to identify different computers on the internet and to know to whom each packet belongs.
The system constantly receives data packets, which consist of the sender's IP, the exact time it was sent, and the size of the packet in bytes. The system can accept them to reach the main server or ignore them. It is based on the parameters $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ to decide which packets to ignore.
It is also possible for the server to receive a new configuration of the parameters $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ at any time.
A packet should be ignored if, in the last $$$\delta$$$ units of time, one or more of the following conditions are met:
- $$$\alpha$$$ or more packets from the same IP have been accepted. - $$$\beta$$$ or more bytes from the same IP have been accepted.
When we talk about the last $$$\delta$$$ units of time, we refer to the moments in time (if the current packet has time $$$t$$$) from $$$t-\delta+1$$$ to $$$t$$$.
For example, if $$$t=8$$$, and $$$\delta=3$$$, only packets at times 6, 7, and 8 would be considered.
An integer $$$T$$$ indicates the number of cases.
For each case, an integer $$$Q$$$, followed by $$$Q$$$ lines with the following format:
First, an integer $$$T_i$$$ denoting the type of query for the $$$i$$$-th line. Followed by the following depending on $$$T_i$$$:
- If $$$T_i$$$ = 1, a string and two integers: IP, current time, and packet size (in bytes) in this order. - If $$$T_i$$$ = 2, three integers: the new values of $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ in this order.
The first line will always be of type 2 to set the initial values of $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$.
All given times are strictly increasing values with respect to previous queries.
For each query of type 1 ($$$T_i$$$ = 1):
- If a packet is accepted, you have to display the line 'ac' on the screen. - If a packet should be ignored, you must display the line 'ig' on the screen.
At the end of each case, put a line with '–'
$$$1 \leq T \leq 5$$$
For every time $$$t$$$ that appears in any query: $$$0 \leq t \leq 10^{12}$$$
For every packet size $$$s$$$ that appears in any query: $$$1 \leq s \leq 10^{12}$$$
For every $$$\alpha$$$, $$$\beta$$$, $$$\delta$$$ that appears in any query: $$$1 \leq \alpha, \beta, \delta \leq 10^{12}$$$
18 points: $$$1 \leq Q \leq 10^4$$$
21 points: $$$1 \leq Q \leq 10^5$$$, $$$\alpha = \beta = 1$$$
29 points: $$$1 \leq Q \leq 10^5$$$, all IPs in a case are the same
32 points: $$$1 \leq Q \leq 10^5$$$
1 4 2 10 7 24 1 253.70.210.43 12158 5 1 253.70.210.43 12162 2 1 253.70.210.43 12170 1
ac ac ig --
1 15 2 2105082674 2007068026 1625093961 1 103.73.59.80 5745 59350582 1 21.2.88.218 5848 417030385 2 4158745174 347394302 820605438 1 33.8.233.115 6002 599300816 2 689106729 77607978 3957107113 1 21.2.88.218 8729 2665793048 1 75.141.72.177 15173 16722561 1 75.141.72.177 22673 3015565887 1 100.226.246.150 23729 2710901173 2 2510564959 2153623029 2464461242 1 23.125.221.98 26766 2777545804 2 3731636496 2747428512 2847248015 1 100.226.246.150 33554 1717343080 1 100.226.246.150 40000 2539933220
ac ac ac ig ac ac ac ac ac ig --
