Protocol buffers（或 protobuf）是一种灵活、高效、自动化的结构化数据序列化机制——可以将其想象为 XML，但它更小、更快、更简单。在本题中，我们将讨论简化版 protocol buffer 的线格式兼容性问题。

Protobuf 描述符

与 XML 或 JSON 不同，protobuf 具有模式（schema）。在实际序列化数据之前，你需要在描述符文件中定义想要序列化的数据结构。以下是一个定义了包含 Car 信息的消息的 protobuf 描述符基本示例：

message Car {
required string brand = 1 ;
required string model = 2 ;
required double max_mileage = 4 ;
optional double max_speed = 3 ;
repeated Accessory accessories = 7 ;
}
message Accessory {
required string name = 1 ;
optional string description = 2 ;
required double price = 3 ;
}

对应的实例数据如下：

brand: "Tesla"
model: "Model 3"
max_mileage: 595
max_speed: 261
accessories {
name: "Body painting"
desctiption: "(Blue)"
price: 10000.0
}
accessories {
name: "Autopilot model"
price: 56000.0
}

给定 protobuf 描述符，我们可以定义 protobuf 实例。消息格式很简单：每种消息类型包含一个或多个唯一编号的字段，每个字段都有一个名称和值类型。值类型可以是整数、浮点数、布尔值、字符串、原始字节，甚至是其他 protocol buffer 消息类型（为简化起见，本题仅考虑 double、string 和嵌套的 protobuf 消息，如示例中的 Accessory），这允许你以层次结构组织数据。

Protobuf 描述符包含一组消息。每条消息包含一组编号字段。每个字段都有自己的字段规则（required、optional 或 repeated）、类型和字段名称（例如示例中的 brand、model、max_mileage）。

字段规则

每个字段具有以下规则之一： required：格式良好的消息必须恰好包含一个此字段。 optional：格式良好的消息可以包含零个或一个此字段（但不能超过一个）。 * repeated：此字段在格式良好的消息中可以重复任意次数（包括零次）。重复值的顺序将被保留。

字段类型

在本题中，我们仅考虑以下类型： double：64 位 IEEE 754 双精度浮点数。 string：任意长度的 UTF-8 编码字符串。 * message：描述符中定义的其他 protobuf 消息类型。

字段编号

每个字段被分配一个唯一编号，该编号是 $1$ 到 $2^{29} - 1$（即 $536,870,911$）之间的整数。

语法

形式上，简化版 protobuf 的语法可以使用扩展巴科斯-诺尔范式（EBNF）指定：

letter = "A" ... "Z" | "a" ... "z"
digit = "0" ... "9"
ident = letter { letter | digit | "_" }
messageName = ident
fieldName = ident
messageType = messageName
decimal = ("1" ... "9") { digit }
fieldNumber = decimal
label = "required" | "optional" | "repeated"
type = "double" | "string" | messageType
field = label type fieldName "=" fieldNumber ";"
messageBody = "{" { field } "}"
message = "message" messageName messageBody
descriptor = { message }

注意：消息名称和字段名称区分大小写，且不能使用保留字（“message”、“required”、“optional”、“repeated”、“double”、“string”）。

Protobuf 编码

本节讨论如何将 protobuf 实例序列化为字节。

Base 128 Varints

Varints 是一种使用一个或多个字节序列化整数的方法。较小的数字占用较少的字节。Varint 中的每个字节（最后一个字节除外）的最高有效位（msb）被置位，表示后续还有字节。每个字节的低 7 位用于存储数字的补码表示，按 7 位一组排列，最低有效组在前。

消息结构

协议缓冲区消息是一系列键值对。消息的二进制版本仅使用字段编号作为键——每个字段的名称和声明类型只能通过在解码端引用消息类型的描述符来确定。

当消息被编码时，键和值被连接成一个字节流。线格式消息中每对的“键”实际上包含两个值：来自 protobuf 描述符文件的字段编号，以及一个提供足够信息以查找后续值长度的线类型（wire type）。在大多数语言实现中，此键被称为标签（tag）。

可用线类型如下：

流式消息中的每个键都是一个 varint，其值为 (field_number << 3) | wire_type。

线格式兼容性问题

如果消息 A 与消息 B 线格式兼容，这意味着消息 A 的任何实例的序列化字节都可以被消息 B 解析，且不会破坏 protobuf 编码假设（且没有未知字段），反之亦然。

输入格式

第一行包含一个整数 $n$，表示 protobuf 描述符的行数。 接下来的 $n$ 行是 protobuf 描述符的内容，其中包含一组消息。每行不超过 120 个字符。 随后是一行包含一个整数 $m$ ($1 \le m \le 50000$)，表示有 $m$ 个线格式兼容性查询。 接下来是 $m$ 行，每行包含一个线格式兼容性查询，包含两个消息名称。

保证描述符是有效的，即：没有两条消息具有相同的名称，消息中没有两个字段具有相同的字段名称或标签编号，且字段中的每个消息类型必须是现有的消息名称之一。 描述符中最多有 1000 条消息，每条消息最多有 16 个字段。 输入的所有标记均以空格分隔。

输出格式

对于每个查询，如果查询中的两条消息线格式兼容，则输出一行 “Wire-format compatible.”；否则，输出 “Wire-format incompatible.”。

样例

输入 1

18
message Test1 {
optional string field = 1 ;
}
message Test2 {
optional string field_string = 1 ;
}
message Test3 {
optional string field = 2 ;
}
message Test4 {
required string field = 1 ;
}
message StringMessage {
optional string field = 1 ;
}
message Test5 {
optional StringMessage field = 1 ;
}
4
Test1 Test2
Test1 Test3
Test1 Test4
Test1 Test5

输出 1

Wire-format compatible.
Wire-format incompatible.
Wire-format incompatible.
Wire-format incompatible.

输入 2

5
message A { optional B nest = 1 ; }
message B { optional C nest = 1 ; }
message C { }
message D { optional E nest = 1 ; }
message E { }
2
B D
A D

输出 2

Wire-format compatible.
Wire-format incompatible.

输入 3

3
message A { optional A nest = 1 ; }
message B { optional C nest = 1 ; }
message C { optional B nest = 1 ; }
3
A B
A C
B C

输出 3

Wire-format compatible.
Wire-format compatible.
Wire-format compatible.

说明

在第一个示例中： 对于 Test1 和 Test2，尽管两条消息的字段名称不同，但序列化消息只关心它们的字段编号。 对于 Test1 和 Test3，虽然两条消息有相同的字段名称，但它们的字段编号不匹配。 对于 Test1 和 Test4，显然 required 与 optional 不兼容。 对于 Test1 和 Test5，并非所有有效的 UTF-8 字符串都是有效的消息，反之亦然。