409072: GYM103430 E Request Throttling

Modern web systems have several layers of protection from attacks. One of such layers is request throttling, which is aimed to keep incoming request rate at a certain level and, therefore, protect the system from DDoS attacks.

Further on, we will consider a simplified IP-based throttling model. In this problem, we will work with IPv4 addresses only. Let's also assume that there are no reserved or internal addresses and the entire IPv4 address space is used.

The next five paragraphs give the formal definition of IPv4 address and IPv4 subnet, respectively. They also describe the structure of the IPv4 address space. These are standard definitions and properties, so if you are familiar with them, you can skip those paragraphs.

An IPv4 address is a 32-bit unsigned integer written in the form $$$a.b.c.d$$$, where each of the values $$$a,b,c,d$$$ is called an octet and is an integer from $$$0$$$ to $$$255$$$ written in decimal notation. For example, the IPv4 address $$$192.168.0.1$$$ can be converted to a 32-bit number using the following expression: $$$192 \cdot 2^{24} + 168 \cdot 2^{16} + 0 \cdot 2^8 + 1 \cdot 2^0$$$. The first octet $$$a$$$ encodes the most significant (leftmost) $$$8$$$ bits, the octets $$$b$$$ and $$$c$$$ — the following blocks of $$$8$$$ bits (in this order), and the octet $$$d$$$ encodes the least significant (rightmost) $$$8$$$ bits.

An IPv4 subnet of size $$$/x$$$ is represented as $$$a.b.c.d/x$$$ (where $$$0 \le x \le 32$$$). A subnet $$$a.b.c.d/x$$$ contains all IPv4 addresses with $$$x$$$ leftmost (most significant) bits equal to $$$x$$$ leftmost bits of the address $$$a.b.c.d$$$. It is required that $$$32 - x$$$ rightmost (least significant) bits of subnet $$$a.b.c.d/x$$$ are zeroes.

Naturally, it happens that all addresses matching subnet $$$a.b.c.d/x$$$ form a continuous range. The range starts with the address $$$a.b.c.d$$$ (its rightmost $$$32 - x$$$ bits are zeroes). The range ends with the address such that its $$$x$$$ leftmost bits equal to $$$x$$$ leftmost bits of address $$$a.b.c.d$$$, and all its $$$32 - x$$$ rightmost bits are ones. A subnet of size $$$/x$$$ contains exactly $$$2^{32-x}$$$ addresses.

For example:

• The subnet $$$192.168.0.0/24$$$ contains a range of $$$256$$$ addresses. $$$192.168.0.0$$$ is the first address of the range, and $$$192.168.0.255$$$ is the last one.
• The subnet $$$172.168.0.70/31$$$ contains two addresses: $$$172.168.0.70$$$ and $$$172.168.0.71$$$.
• The subnet $$$10.8.179.3/32$$$ contains only one address: $$$10.8.179.3$$$.

The entire IPv4 address space consists of $$$2^{32}$$$ IP addresses. In the terms of subnets, it means there are $$$2^{32}$$$ different $$$/32$$$ subnets (because each $$$/32$$$ subnet contains exactly one IP address), $$$2^{31}$$$ different $$$/31$$$ subnets (each $$$/31$$$ subnet contains two addresses), and so on, $$$2^1 = 2$$$ different $$$/1$$$ subnets, and $$$2^0 = 1$$$ subnet of size $$$/0$$$. Furthermore, it can be noted that each IP address is contained in exactly one subnet of each size from $$$/0$$$ to $$$/32$$$ inclusive. Further on, such subnets will be called parent subnets. E.g. these are some of the parent subnets of the IPv4 address $$$192.168.21.5$$$: $$$192.168.21.5/32$$$, $$$192.168.21.4/30$$$, $$$192.168.21.0/24$$$, $$$192.168.16.0/21$$$, $$$192.168.0.0/16$$$, $$$192.0.0.0/8$$$, $$$128.0.0.0/1$$$, $$$0.0.0.0/0$$$.

The request throttling model is described by $$$33$$$ integers $$$t_0, t_1, \ldots, t_{32}$$$ — the throttling limits for $$$/0, /1, \ldots, /32$$$ subnets, respectively. In other words, $$$t_j$$$ is the maximum number of requests from the certain subnet of size $$$/j$$$ which are allowed to bypass the throttling subsystem and reach other layers of the system. The throttling limit for each of $$$2^j$$$ subnets of size $$$/j$$$ is equal to the same number $$$t_j$$$, but passed request count is calculated separately for each individual subnet.

Incoming requests are processed one by one. When a request arrives, its source IP address is analyzed, and if the address is within the throttling limits of all $$$33$$$ of its parent subnets, then the request is allowed. It goes through the throttling system, increasing the passed request count for all its parent subnets. Otherwise, the request is blocked and the passed request count for no subnet is increased. We assume that a request is within the throttling limits of a subnet if and only if the passed request count of that subnet is strictly less than the throttling limit for the subnet (i.e. the value of $$$t_j$$$ for the corresponding size of the subnet).

Your task is to emulate the work of the throttling subsystem. You are given $$$n$$$ incoming requests, where each request is characterized by its source IP address $$$s_i$$$. The requests should be processed in the order they are given. For each request, print "a" (without quotes) if the request is allowed, and "b" (also without quotes) if the request is blocked.

The first line of the input file contains $$$33$$$ integers $$$t_0, t_1, \ldots, t_{32}$$$ — the throttling limits for $$$/0, /1, \ldots, /32$$$ subnets, respectively: $$$1 \le t_j \le 10^9$$$ for $$$0 \le j \le 32$$$.

The second line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of requests. The following $$$n$$$ lines describe the source addresses of the requests. It is guaranteed that each source address represents an IPv4 address in the correct format. It is assumed that there are no reserved IPv4 addresses and the entire IPv4 address space can be used.

Output file should contain exactly $$$n$$$ lines, the $$$i$$$-th line should contain a single lowercase letter "a" (without quotes) if the $$$i$$$-th request is allowed, or a single lowercase letter "b" (without quotes) if the $$$i$$$-th request is blocked.

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 3 2
5
192.168.0.1
192.168.0.1
192.168.0.1
192.168.0.0
192.168.0.0

a
a
b
a
b

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 2 10 10 10 10 10 10 10 10
6
5.5.5.0
5.5.5.1
5.5.5.2
5.5.255.255
5.5.255.0
5.5.255.128

a
a
b
a
a
b

In both examples, the first line with $$$33$$$ numbers can't fit on a printed sheet. For this reason, the line is split in two. In the tests on which your submission will be tested, exactly $$$33$$$ numbers are given in the first line.

In the first example, only limits for $$$/31$$$ and $$$/32$$$ subnets actually influence the throttling, since limits for other subnets are greater than the total number of requests. The first two requests from $$$192.168.0.1$$$ are allowed, as they are within the limits for $$$192.168.0.1/32$$$ and $$$192.168.0.0/31$$$ subnets. The third request from $$$192.168.0.1$$$ is within the limits for $$$192.168.0.0/31$$$ subnet ($$$2$$$ out of $$$3$$$ requests were passed, one more still can be passed), but already exceeds the limits for $$$192.168.0.1/32$$$ ($$$2$$$ out of $$$2$$$ requests were already passed). Since the request exceeds the limit for at least one subnet, it is blocked, without affecting the limits for other requests. The next request from $$$192.168.0.0$$$ is within the limits both for $$$192.168.0.0/31$$$ and $$$192.168.0.0/32$$$ subnets, so it is allowed. The last request from $$$192.168.0.0$$$ is within the limits for $$$192.168.0.0/32$$$ subnet ($$$1$$$ out of $$$2$$$ requests are passed), but the limit for $$$192.168.0.0/31$$$ subnet is already exceeded, so the request is blocked.

The second example demonstrates that two $$$/24$$$ subnets ($$$5.5.5.0/24$$$ and $$$5.5.255.0/24$$$) are independent, and requests are counted separately for them.