← 返回题目列表

AtCoder · ttpc2023_l

L. 下一个 TTPC 3

中文机器翻译题面 查看原题

配点 : 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