Выбор версии по ограничению Composer

Для каждого ограничения версии выберите наибольшую подходящую из доступных версий X.Y.Z. Правила:

• ^A.B.C: >=A.B.C и меньше следующей версии, где меняется первая ненулевая часть (^1.2.3 → <2.0.0, ^0.3.1 → <0.4.0, ^0.0.3 → <0.0.4); недостающие части считаются нулями, но ^0.3 → <0.4.0, ^0 → <1.0.0, ^1 → <2.0.0;
• ~A.B.C → >=A.B.C <A.(B+1).0; ~A.B и ~A → <(A+1).0.0;
• A.B.* → >=A.B.0 <A.(B+1).0; A.* → >=A.0.0 <(A+1).0.0;
• A.B.C: ровно эта версия.

Ввод: n (n ≤ 5000), затем строки: ограничение и до 20 версий через пробел.

Вывод: выбранная версия или none.

Пример

5
^2.3 2.2.9 2.3.0 2.9.1 3.0.0
~1.2.3 1.2.2 1.2.9 1.3.0
^0.3 0.3.5 0.4.0
1.0.* 1.0.7 1.1.0
~1.2 1.9.9 2.0.0

2.9.1
1.2.9
0.3.5
1.0.7
1.9.9