Berkomnadzor

题意翻译

### 题目描述 联邦通信、信息技术和大众传媒监督局(Berkomnadzor)是伯利兹联邦执行机构,负责保护伯利兹普通居民免受现代互联网的威胁。 Berkomnadzor 拥有一份禁止使用的 IPv4 子网名单(黑名单)和一份允许使用的 IPv4 子网名单(白名单)。柏克兰的所有互联网服务提供商(ISP)都必须配置网络设备,阻止访问符合黑名单的所有 IPv4 地址。同时,ISP 必须允许(即不阻止)所有符合白名单的 IPv4 地址访问。如果某个 IPv4 地址与上述两个列表都不匹配,则由 ISP 决定是否阻止该地址。当且仅当一个 IPv4 地址与黑名单(白名单)中的某个子网相匹配时,它才会与黑名单(白名单)相匹配。一个 IPv4 地址可以同时属于白名单和黑名单,这种情况会导致矛盾(见输出描述中的无解情况)。 IPv4 地址是一个 32 位无符号整数,书写形式为 $a.b.c.d$,其中每个值 $a,b,c,d $ 称为一个八位位组,是一个从 $0 $ 到 $255 $ 的十进制整数。例如,IPv4 地址 $ 192.168.0.1 $ 可以用以下表达式转换为 32 位数字 $ 192 \cdot 2^{24} + 168 \cdot 2^{16} + 0 \cdot 2^8 + 1 \cdot 2^0 $ 。第一个八位位组 $ a $ 编码最有意义(最左边的 $ 8 $ 位),八位位组 $ b $ 和 $ c $ 下面的 $ 8 $ 位块次有意义(按此顺序),八位位组 $ d $ 编码最无意义(最右边的 $ 8 $ 位)。 伯兰的 IPv4 网络与世界其他地方略有不同。伯兰没有保留地址或内部地址,而是使用所有可能的 $ 2^{32} $ 值。 一个 IPv4 子网用 $ a.b.c.d $ 或 $ a.b.c.d/x $ 表示(其中 $ 0 \le x \le 32 $ )。子网 $ a.b.c.d $ 包含一个地址 $ a.b.c.d $ 。一个子网 $ a.b.c.d/x $ 包含所有最左边(最重要)位 $ x $ 等于地址 $ a.b.c.d $ 最左边位 $ x $ 的 IPv4 地址,要求子网 $ a.b.c.d/x $ 最右边(最不重要)位 $ 32 - x $ 为 0。 与子网 $ a.b.c.d/x $ 匹配的所有地址自然会形成一个连续的范围。该范围从地址 $ a.b.c.d $ 开始(其最右边的 $ 32 - x $ 位为零)。该范围以地址 $ a.b.c.d $ 的最左端 $ x $ 位等于地址 $ a.b.c.d $ 的最左端 $ x $ 位,且其最右端 $ 32 - x $ 位全为 1 的地址结束。子网恰好包含 $ 2^{32-x} $ 地址。子网 $ a.b.c.d/32 $ 恰好包含一个地址,也可以只用 $ a.b.c.d $ 表示。 例如,子网 $ 192.168.0.0/24 $ 包含 256 个地址。$ 192.168.0.0 $ 是地址范围的第一个地址,$ 192.168.0.255 $ 是最后一个地址。 Berkomnadzor 的工程师制定了一项提高 Berland 全球网络性能的计划。他们不想同时维护白名单和黑名单,而只想建立一个包含最少子网数量的优化黑名单。这样做的目的是阻止所有符合优化黑名单的 IPv4 地址,并允许所有其他地址访问。当然,旧黑名单中的 IPv4 地址必须继续封锁,而旧白名单中的所有 IPv4 地址必须继续允许。那些既不符合旧黑名单也不符合旧白名单的 IPv4 地址,无论其以前是否可以访问,都可以被阻止或允许。 请编写一个程序,将黑名单和白名单作为输入,并生成优化黑名单。优化后的黑名单必须包含尽可能少的子网,并满足上述所有 IPv4 地址可访问性要求。 源列表中的 IPv4 子网可以任意交叉。如果某个 IPv4 地址同时符合源白名单和黑名单,请输出一个数字-1。 ### 输入格式 输入的第一行包含一个整数 $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) - 输入中 IPv4 子网的总数。 下面的 $ n $ 行包含 IPv4 子网。每行以"-"或 "+"符号开头,表示该子网属于黑名单还是白名单。其后是 IPv4 子网,格式为 $ a.b.c.d $ 或 $ a.b.c.d/x $($ 0 \le x \le 32 $),不留空格。黑名单总是包含至少一个子网。 输入中给出的所有 IPv4 子网都是有效的。整数不以额外的前导零开头。所提供的 IPv4 子网可以任意交叉。 ### 输出格式 如果存在同时符合白名单和黑名单的 IPv4 地址,则输出 -1。否则输出 $ t $ - 优化后黑名单的长度,然后是 $ t $ 子网,每个子网在新的一行。子网可以任意顺序打印。所有与源黑名单匹配的地址必须与优化黑名单匹配。所有与源白名单匹配的地址必须与优化黑名单不匹配。打印子网 $ a.b.c.d/32 $ 的方式有两种:$ a.b.c.d/32 $ 或 $ a.b.c.d $ 。 如果有多个解决方案,则输出任意一个。

题目描述

Berkomnadzor — Federal Service for Supervision of Communications, Information Technology and Mass Media — is a Berland federal executive body that protects ordinary residents of Berland from the threats of modern internet. Berkomnadzor maintains a list of prohibited IPv4 subnets (blacklist) and a list of allowed IPv4 subnets (whitelist). All Internet Service Providers (ISPs) in Berland must configure the network equipment to block access to all IPv4 addresses matching the blacklist. Also ISPs must provide access (that is, do not block) to all IPv4 addresses matching the whitelist. If an IPv4 address does not match either of those lists, it's up to the ISP to decide whether to block it or not. An IPv4 address matches the blacklist (whitelist) if and only if it matches some subnet from the blacklist (whitelist). An IPv4 address can belong to a whitelist and to a blacklist at the same time, this situation leads to a contradiction (see no solution case in the output description). 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, 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 $ . 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. The IPv4 network in Berland is slightly different from the rest of the world. There are no reserved or internal addresses in Berland and use all $ 2^{32} $ possible values. An IPv4 subnet is represented either as $ a.b.c.d $ or as $ a.b.c.d/x $ (where $ 0 \le x \le 32 $ ). A subnet $ a.b.c.d $ contains a single address $ a.b.c.d $ . 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 address $ a.b.c.d $ (its rightmost $ 32 - x $ bits are zeroes). The range ends with address which $ x $ leftmost bits equal to $ x $ leftmost bits of address $ a.b.c.d $ , and its $ 32 - x $ rightmost bits are all ones. Subnet contains exactly $ 2^{32-x} $ addresses. Subnet $ a.b.c.d/32 $ contains exactly one address and can also be represented by just $ a.b.c.d $ . For example subnet $ 192.168.0.0/24 $ contains range of 256 addresses. $ 192.168.0.0 $ is the first address of the range, and $ 192.168.0.255 $ is the last one. Berkomnadzor's engineers have devised a plan to improve performance of Berland's global network. Instead of maintaining both whitelist and blacklist they want to build only a single optimised blacklist containing minimal number of subnets. The idea is to block all IPv4 addresses matching the optimised blacklist and allow all the rest addresses. Of course, IPv4 addresses from the old blacklist must remain blocked and all IPv4 addresses from the old whitelist must still be allowed. Those IPv4 addresses which matched neither the old blacklist nor the old whitelist may be either blocked or allowed regardless of their accessibility before. Please write a program which takes blacklist and whitelist as input and produces optimised blacklist. The optimised blacklist must contain the minimal possible number of subnets and satisfy all IPv4 addresses accessibility requirements mentioned above. IPv4 subnets in the source lists may intersect arbitrarily. Please output a single number -1 if some IPv4 address matches both source whitelist and blacklist.

输入输出格式

输入格式


The first line of the input contains single integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — total number of IPv4 subnets in the input. The following $ n $ lines contain IPv4 subnets. Each line starts with either '-' or '+' sign, which indicates if the subnet belongs to the blacklist or to the whitelist correspondingly. It is followed, without any spaces, by the IPv4 subnet in $ a.b.c.d $ or $ a.b.c.d/x $ format ( $ 0 \le x \le 32 $ ). The blacklist always contains at least one subnet. All of the IPv4 subnets given in the input are valid. Integer numbers do not start with extra leading zeroes. The provided IPv4 subnets can intersect arbitrarily.

输出格式


Output -1, if there is an IPv4 address that matches both the whitelist and the blacklist. Otherwise output $ t $ — the length of the optimised blacklist, followed by $ t $ subnets, with each subnet on a new line. Subnets may be printed in arbitrary order. All addresses matching the source blacklist must match the optimised blacklist. All addresses matching the source whitelist must not match the optimised blacklist. You can print a subnet $ a.b.c.d/32 $ in any of two ways: as $ a.b.c.d/32 $ or as $ a.b.c.d $ . If there is more than one solution, output any.

输入输出样例

输入样例 #1

1
-149.154.167.99

输出样例 #1

1
0.0.0.0/0

输入样例 #2

4
-149.154.167.99
+149.154.167.100/30
+149.154.167.128/25
-149.154.167.120/29

输出样例 #2

2
149.154.167.99
149.154.167.120/29

输入样例 #3

5
-127.0.0.4/31
+127.0.0.8
+127.0.0.0/30
-195.82.146.208/29
-127.0.0.6/31

输出样例 #3

2
195.0.0.0/8
127.0.0.4/30

输入样例 #4

2
+127.0.0.1/32
-127.0.0.1

输出样例 #4

-1