配点 : 100 点
东京工业大学编程竞赛是 1 年 1 次举行的竞赛编程比赛。有一个英文大写字符串 S_1, S_2, S_3, S_4 ,从明年起,也就是正整数 x 反对 x 年后举行的东京工业大学编程竞赛简称 T_x 的决定方法如下。
- T_x 是 您也可以写 4 是由英文字母大写组成的字符串
- T_x 可以得到第 i 文字目 (1 \le i \le 4) 是 您也可以写 S_i 可以得到第 ((x - 1) \bmod |S_i|) + 1 与第几字符相等( |S_i| 是一个字符串 让它代表 S_i 长度)
正整数 N 。
对于N 次简称为 TTPC 的将会是几年后?
制約
- 1 \le N \le 10^6
- 1 \le |S_i| \le 10^3\ (1 \le i \le 4)
- N 是一个整数
- S_i 是仅由英文字母大写组成的字符串
部分点
- 附加限制 如果正确答案是满足 |S_i| \leq 50\ (1 \le i \le 4) 的数据集 给出 15 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N S_1 S_2 S_3 S_4
出力
下面 2 满足的正整数 x 输出该数。如果不存在这样的 x ,则改为 -1 。
- T_x = {}
TTPC - T_1, T_2, \dots, T_x 中的字符串
出现
TTPC是 您也可以写 N 次 因为是
入力例 1
3 TTPC TLE P AC
出力例 1
34
1 次简称为 TTPC 是
仅当 10 年後、 2 次简称为 TTPC 是
仅当 22 年後、 3 次简称为 TTPC 是
仅当 34 年后,所以答案是 34 。
入力例 2
670055 TF OITFKONTO GFPPNPWTZP CCZFB
出力例 2
-1
的缩写
不会成为 TTPC 。
入力例 3
910359 TOKYO TECH PROGRAMMING CONTEST
出力例 3
1401951321