Hide

Problem K
Knight Search

Alice is a chess knight living in Chessland (an $N \times N$ board). The cells in Chessland are numbered from $1$ to $N^2$ in row major order. Each cell has an UPPERCASE alphabet character assigned to it. The Chessland is described by a string $S$ of length $N^2$ (in row major order). For example for $N = 5$ and $S$ = “IXIXXXXCXAXSXXPXXCSXAGXXX”, the Chessland that Alice lives in looks like this:

  12345
  -----
1|IXIXX
2|XXCXA
3|XSXXP
4|XXCSX
5|AGXXX

As Alice is a chess knight, she can only move from cell $(a, b)$ to cell $(c, d)$ in Chessland if and only if $(a-c)^2 + (b-d)^2 = 5$. Alice wonder if she can find her favorite string “ICPCASIASG” in Chessland by starting from a cell with character ‘I’ and finds the other $9$ characters by jumping around in Chessland using chess knight movements. Alice can visit the same cell more than once.

You are of course Bob the computing bee and your job is to help her decide the answer.

Input

The first line of input consists of 1 integer: $N$ ($1 \leq N \leq 100$). The second line contains a string $S$ of $N^2$ UPPERCASE characters [‘A’..‘Z’] that describe Chessland.

Output

Print “YES” if Alice can find string “ICPCASIASG” in Chessland or print “NO” otherwise.

Sample Input 1 Sample Output 1
5
IXIXXXXCXAXSXXPXXCSXAGXXX
YES
Sample Input 2 Sample Output 2
5
THEQUICKBROWNFOXJUMPSOVER
NO

Please log in to submit a solution to this problem

Log in