H - TTPC Never Ends 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Let’s consider abbreviating a programming contest held once a year using a sequence of four uppercase English letters. This year's abbreviation is TTPC!

Problem Statement

The abbreviation-deciding machine \mathrm{M} for a programming contest has a string S of length N consisting of uppercase English letters and an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
Additionally, machine \mathrm{M} has four cursors numbered from 1 to 4 for pointing at characters in S. Initially, for each i = 1, 2, 3, 4, cursor i points to the x_i-th character of S.

The machine \mathrm{M} has two buttons: the Abbreviation Button and the Update Button. Pressing these buttons triggers the following actions:

  • Abbreviation Button: Machine \mathrm{M} outputs a string of length 4 formed by concatenating the characters pointed to by cursors 1, 2, 3, 4 in this order.
  • Update Button: For each i = 1, 2, 3, 4, the following happens:
    • Let y be the current position of cursor i. Cursor i moves from the y-th character of S to the A_y-th character of S.

This year's programming contest abbreviation was determined by pressing the Abbreviation Button, resulting in TTPC. Here, "this year" refers to 0 years from now.

Starting from next year, the abbreviation for the programming contest each year will be obtained through the following steps:

  1. Press the update button.
  2. Press the abbreviation button to determine the abbreviation.

How many years from now will the abbreviation return to TTPC for the last time? Will the end of TTPC come?

Constraints

  • N, A_i, x_1, x_2, x_3, x_4 are integers.
  • 3 \leq N \leq 50
  • S is a string of length N consisting of uppercase English letters.
  • 1 \leq A_i \leq N\ (1 \leq i \leq N)
  • 1 \leq x_1, x_2, x_3, x_4 \leq N
  • S_{x_1} = {}T
  • S_{x_2} = {}T
  • S_{x_3} = {}P
  • S_{x_4} = {}C

Input

The input is given in the following format:

N
S
A_1 A_2 \dots A_N
x_1 x_2 x_3 x_4

Output

Output a non-negative integer k satisfying the following conditions. If such a k does not exist, output NeverEnds instead.

  • The abbreviation becomes TTPC k years from now.
  • For any integer l > k, the abbreviation does not become TTPC l years from now.

Sample Input 1

5
TTTPC
2 3 4 4 5
1 2 4 5

Sample Output 1

1
  • 0 years from now, the abbreviation is TTPC, and the cursor positions are (1,2,4,5).
  • 1 year from now, the abbreviation is TTPC, and the cursor positions are (2,3,4,5).
  • 2 years from now, the abbreviation is TPPC, and the cursor positions are (3,4,4,5).
  • 3 years from now, the abbreviation is PPPC, and the cursor positions are (4,4,4,5).

The last time the abbreviation becomes TTPC is 1 year from now.

Sample Input 2

4
TTPC
2 3 4 1
1 2 3 4

Sample Output 2

NeverEnds

The abbreviation becomes TTPC at years 0, 4, 8, 12, \dots and so on. TTPC never ends.

Sample Input 3

6
TTPCZT
5 3 2 6 4 4
1 2 3 4

Sample Output 3

0

配点 : 100 点

1 年に 1 回行われるプログラミングコンテストの略称を、英大文字を 4 つ並べて得ることを考えましょう。今年の略称は TTPC です！

問題文

プログラミングコンテストの略称決めマシーン \mathrm{M} は、英大文字からなる長さ N の文字列 S と長さ N の整数列 A = (A_1, A_2, \dots, A_N) を持っています。 また、マシーン \mathrm{M} は S の中の文字を指し示すためのカーソルを 4 つ持っており、それぞれ 1 から 4 までの番号がついています。 はじめ、i = 1, 2, 3, 4 のそれぞれについて、カーソル i は S の x_i 文字目を指しています。

\mathrm{M} には 2 つのボタン 略称決めボタン と 更新ボタン がついています。このボタンを押すと、それぞれ以下のことが起こります。

  • 略称決めボタン: マシーン \mathrm{M} は、カーソル 1, 2, 3, 4 が指している文字をこの順につなげた長さ 4 の文字列を出力する。
  • 更新ボタン: i = 1, 2, 3, 4 のそれぞれについて以下が起こる。
    • 現在カーソル i が指している文字を S の y 文字目とする。カーソル i が指す文字が、S の y 文字目から S の A_y 文字目に変わる。

略称決めボタンを押して得た文字列を今年のプログラミングコンテストの略称としたところ、TTPC に決まりました。ただし、今年とは今から 0 年後のことです。

来年以降毎年行われるプログラミングコンテストの略称は、次の手順で得ることにします。

  1. 更新ボタンを押す。
  2. 略称決めボタンを押して得た文字列を略称とする。

最後に略称が TTPC になるのは今から何年後のことでしょうか？それとも TTPC の終わりは来ないのでしょうか？

制約

  • N,A_i,x_1,x_2,x_3,x_4 は整数
  • 3\le N\le 50
  • S は英大文字からなる長さ N の文字列
  • 1\le A_i\le N\ (1\le i\le N)
  • 1\le x_1,x_2,x_3,x_4\le N
  • S_{x_1}={}T
  • S_{x_2}={}T
  • S_{x_3}={}P
  • S_{x_4}={}C

入力

入力は以下の形式で標準入力から与えられる。

N
S
A_1 A_2 \dots A_N
x_1 x_2 x_3 x_4

出力

以下の条件を満たす非負整数 k を出力せよ。そのような k が存在しない場合は、代わりに NeverEnds と出力せよ。

  • k 年後に略称が TTPC となる。
  • k より大きい任意の整数 l について、l 年後の略称は TTPC ではない。

入力例 1

5
TTTPC
2 3 4 4 5
1 2 4 5

出力例 1

1
  • 今から 0 年後の略称は TTPC で、カーソルの位置は (1,2,4,5) です。
  • 今から 1 年後の略称は TTPC で、カーソルの位置は (2,3,4,5) です。
  • 今から 2 年後の略称は TPPC で、カーソルの位置は (3,4,4,5) です。
  • 今から 3 年後の略称は PPPC で、カーソルの位置は (4,4,4,5) です。

最後に略称が TTPC になるのは 1 年後です。

入力例 2

4
TTPC
2 3 4 1
1 2 3 4

出力例 2

NeverEnds

0,4,8,12,\dots 年後に略称が TTPC となります。TTPC は終わりません。

入力例 3

6
TTPCZT
5 3 2 6 4 4
1 2 3 4

出力例 3

0