题目内容

云化平台对于组件按版本号进行统一管理，版本号遵循语义版本控制系统，格式为：

major.minor.patch

其中

• major：项目进行重大更新，且包含不向后兼容的功能
• minor：仅在以向后兼容的方式添加新功能
• patch：仅在以向后兼容的方式修复错误，并且没有添加任何新的功能

业务 App 在其配置文件中声明其依赖的组件及版本，如 1.1.0

并且版本号可以缩写，没有写出来的部分表示为0，如：

对于其依赖的版本号，有三种声明方式：

1. 指定最新版本

   业务 App 的配置方式为：*

   它最终会匹配仓库中的最新版本给业务 App 使用。

2. 取 major 版本一致情况下的最大版本

   由于 major 版本之间可能不兼容，指定主版本号，业务 App 的配置方式为：^1.2.0

   这样写会尝试匹配主版本号为1的最大版本。

更多样例含义：

保证 major 和 minor 版本一致，只取最新的 patch 版本，写法为：

只进行Bug修复，只更新 patch，业务 App 的配置方式为：~1.2.0 或者 -1.2.0

这样写会取 major 版本号为1、minor 版本2、patch 版本号最大的版本。

输入描述

第一行给出当前仓库中指定组件的版本数量 N ，后续 N 行给出具体的每一个版本号(注意这里不保证版本号的大小顺序)，最后一行给出业务 App 组件的版本号声明。

3 <= N <= 100000 )

版本号中的 major、minor 和 patch 都满足 0 <= version <= 100000

输出描述

输出最终匹配到的版本号。

如果没有配置的版本号则输出 None

样例1

输入

5
1.1.1
2.1
1.2.2
1.2.6
1.3.3
^1.2

输出

1.3.3

说明

对于目标组件，当前在仓库中有5个版本，分别为 1.1.1 2.1 1.2.2 1.2.6 1.3.3

业务 App 声明的组件依赖为 ^1.2，系统最终为其匹配到的版本为1.3.3

样例2

输入

5
1.1.1
2.1
1.2.2
1.2.6
1.3.3
*

输出

2.1

说明

*表示取所有版本中的最高版本，即2.1

样例3

输入

6
1.1.1
2.1
1.2.2
1.2.6
1.3.3
1.4.0
-1.2

输出

1.2.6

说明

-表示在 major.minor 不变的情况下取 patch 最大的版本号，这里 即：1.2.6

样例4

输入

6
1.1.1
2.1
1.2.2
1.2.6
1.3.3
1.4.0
^1.0

输出

None

说明

major 版本号为1 minor 大于等于6的版本号不存在，输出None