#P18493. Next TTPC 3

Next TTPC 3

Next TTPC 3

TokyoTech Programming Contest 是一年一度的程序设计竞赛。给定四个由大写英文字母组成的字符串 S1,S2,S3,S4S_1,S_2,S_3,S_4。从明年开始,xx 年后举行的比赛的缩写 TxT_x 按以下规则确定:

  • TxT_x 是长度为 44 的大写英文字符串。
  • 对 1≤i≤41\le i\le4,TxT_x 的第 ii 个字符等于 SiS_i 的第 ((x−1) mod ∣Si∣)+1((x-1)\bmod |S_i|)+1 个字符。这里 ∣Si∣|S_i| 表示 SiS_i 的长度,字符下标从 11 开始。

给定正整数 NN,求经过多少年,缩写会第 NN 次成为 TTPC?

输入格式

N
S1
S2
S3
S4

NN 为整数,满足 1≤N≤1061\le N\le10^6。对每个 1≤i≤41\le i\le4,1≤∣Si∣≤10001\le |S_i|\le1000,且 SiS_i 仅含大写英文字母。

输出格式

输出满足以下两个条件的正整数 xx;如果不存在这样的 xx,输出 -1。

  • TxT_x 为 TTPC。
  • TTPC 在 T1,T2,…,TxT_1,T_2,\ldots,T_x 中恰好出现 NN 次。

样例 1

输入:

3
TTPC
TLE
P
AC

输出:

34

缩写分别在 10,22,3410,22,34 年后第一次、第二次、第三次成为 TTPC,所以答案为 3434。

样例 2

输入:

670055
TF
OITFKONTO
GFPPNPWTZP
CCZFB

输出:

-1

这个例子中,缩写永远不会成为 TTPC。

样例 3

输入:

910359
TOKYO
TECH
PROGRAMMING
CONTEST

输出:

1401951321