P16697 [CSPro 29] Interstellar Network II

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: .

With the further construction and expansion of the interstellar network, a new problem has appeared for network engineers: the address space is not enough! Originally, the interstellar network used the traditional IPv6 protocol. Although it provides about $2^{128}$ available addresses, when facing the vast universe and the explosive growth of network users, even such a huge address space will one day be exhausted. The development of a new communication protocol was assigned to the famous holy land of network technology—Xixiaifu Star. Finally, after 2333 years of unremitting effort, the engineers of Xixiaifu Star designed a new protocol—the “Xixiaifu IP Protocol”, also called IPxxaf. In the IPxxaf protocol, an address consists of $n$ binary bits, where $n$ is a multiple of $16$. For daily representation, it uses a hexadecimal notation similar to IPv6, with every $4$ bits separated by `:`. For example, when $n = 32$, the address is `2a00:0001`, which represents the binary address `0010 1010 0000 0000 0000 0000 0000 0001`. Note that there will be no cases like IPv6 where leading `0` in each group is omitted, or a segment of `0` is omitted using `::`. For convenience, let $\text{num}(s)$ denote the $n$-bit binary number of address $s$ with higher bits first and lower bits last. A “continuous block of addresses” refers to a series of addresses whose $\text{num}(s)$ values form a continuous interval. The network administrator of Xixiaifu Star is responsible for address allocation and management. At the beginning, the entire address space is unallocated. Users may apply to the administrator for some addresses at any time: - `1 id l r`: User $\text{id}$ applies for a continuous address block within the range $l \sim r$ (including $l$ and $r$, same below). During an address application, the administrator must first check whether the addresses are available. If all requested addresses are unallocated, the check passes; if there exists any address that has already been allocated to other users, the check fails. However, there is a special case: none of the requested addresses has been allocated to other users, but some of them were previously allocated to the same user. In this case, the check can be considered passed; but if all requested addresses were previously allocated to this user, then the check fails. If the above check passes, the administrator returns `YES` and allocates the requested addresses to the user. Otherwise, the administrator returns `NO` and does not change the existing allocation. The network administrator also needs to periodically check address allocation status. Specifically, there are the following two operations: - `2 s`: Query which user address $s$ is allocated to. If unallocated, the result is $0$. - `3 l r`: Check whether all addresses in the range $l \sim r$ are completely allocated to a single user. If yes, output that user’s id; otherwise, output $0$. During the operation of the whole network, there are $q$ applications and queries in total. As an important network technical consultant on Xixiaifu Star, you need to process each operation in order and output the corresponding result.

Read from standard input. The first line contains $2$ positive integers $n, q$. The next $q$ lines each contain one operation in the formats described above. Here $\text{id}$ is a positive integer, and $l, r, s$ are all IPxxaf address strings, where hexadecimal digits use numbers and lowercase letters.

Write to standard output. Output $q$ lines. Each line is a non-negative integer or a string, representing the result of the operation. For operation $1$, output `YES` or `NO`. For operations $2, 3$, output a non-negative integer.

### Explanation of Sample 1 At the 4th operation, part of the addresses applied by user $2$ had already been allocated to user $1$, so the application fails. At the 6th operation, all addresses applied by user $1$ had already been allocated to user $1$, so the application fails. At the 11th operation, part of the addresses applied by user $1$ had already been allocated to user $1$, and the remaining addresses were still unallocated, so the application succeeds. ### Constraints For all data, $n \le 512$, $q \le 5 \times 10^4$, $n$ is a multiple of $16$, $\text{id} \le q$. For operations $1,3$, it is guaranteed that $\text{num}(l) \le \text{num}(r)$. | Test Point ID | $n \le$ | $q \le$ | Special Properties | |:-------------:|:-------:|:---------:|:------------------:| | $1 \sim 4$ | $16$ | $200$ | None | | $ 5 \sim 6 $ | $ 64$ | ^ | ^ | | $7 \sim 9$ | $512$ | ^ | ^ | | $10 \sim 11$ | $16$ | $20000$ | ^ | | $12 \sim 13$ | $64$ | $50000$ | ^ | | $14 \sim 16$ | $512$ | ^ | For all operations $1$, all $\text{id}$ are pairwise distinct | | $17 \sim 20$ | ^ | ^ | None | Translated by ChatGPT 5