E. Entanglement
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are two schools $$$\text{G}$$$ and $$$\text{H}$$$ with $$$N$$$ and $$$M$$$ buildings respectively. For a pair of buildings inside the same school, there might be a undirected road between them. Every two buildings in a school are reachable via roads. The $$$i$$$-th building in $$$\text{G}$$$ has a number $$$g_i$$$ describing its type. Similarly, the $$$i$$$-th building in $$$\text{H}$$$ has a number $$$h_i$$$.

Define a "$$$\text{G}$$$-tour" to be a sequence $$$(t_1, t_2, \dots, t_k)$$$ such that for each $$$1 \le i \le k - 1$$$, the buildings $$$t_i$$$ and $$$t_{i+1}$$$ have a road between them. (In other words, it is a walk on the graph $$$\text{G}$$$.) The "characteristic" of a $$$\text{G}$$$-tour is the list of numbers on the buildings, which is $$$(g_{t_1}, g_{t_2}, \dots, g_{t_k})$$$. Define an "$$$\text{H}$$$-tour" similarly.

Suppose $$$L$$$ is an integer such that there exist a $$$\text{G}$$$-tour $$$(a_1, a_2, \dots, a_L)$$$ and an $$$\text{H}$$$-tour $$$(b_1, b_2, \dots, b_L)$$$ satisfying:

  • They are both of length $$$L$$$.
  • Their characteristics are the same.
  • For each $$$1 \le i \le L - 2$$$, $$$a_i = a_{i+2}$$$ and $$$b_i = b_{i+2}$$$ cannot both be true.

Output the maximum possible $$$L$$$, or INF if $$$L$$$ can be arbitrarily large.

Input

Line $$$1$$$ contains an integer $$$N$$$ ($$$1 \le N \le 2000$$$).

Line $$$2$$$ contains $$$N$$$ integers $$$g_1, g_2, \dots, g_N$$$ ($$$1 \le g_i \le 2000$$$).

Line $$$3 \sim (N+2)$$$ each contains a 01-string of length $$$N$$$, representing the graph $$$\text{G}$$$. $$$\text{G}_{ij} = 1$$$ iff $$$i$$$-th node and $$$j$$$-th node are directly connected in graph $$$\text{G}$$$. Note that $$$\text{G}_{ij} = \text{G}_{ji}$$$.

Line $$$(N+3)$$$ contains an integer $$$M$$$ ($$$1 \le M \le 2000$$$).

Line $$$(N+4)$$$ contains $$$M$$$ integers $$$h_1, h_2, \dots, h_M$$$ ($$$1 \le h_i \le 2000$$$).

Line $$$(N+5) \sim (N+M+4)$$$ each contains a 01-string of length $$$M$$$, representing the graph $$$\text{H}$$$. $$$\text{H}_{ij} = 1$$$ iff $$$i$$$-th node and $$$j$$$-th node are directly connected in graph $$$\text{H}$$$. Note that $$$\text{H}_{ij} = \text{H}_{ji}$$$.

Output

Output the maximum possible $$$L$$$, or INF if $$$L$$$ can be arbitrarily large.

Scoring
  • Subtask 1 (12 points): For all $$$1 \le i \le N$$$, $$$g_i = 1$$$; for all $$$1 \le j \le M$$$, $$$h_j = 1$$$; both graphs are chains.
  • Subtask 2 (20 points): For all $$$1 \le i \le N$$$, $$$g_i = 1$$$; for all $$$1 \le j \le M$$$, $$$h_j = 1$$$.
  • Subtask 3 (26 points): $$$1 \le N, M \le 60$$$; for all $$$1 \le i \le N$$$, $$$g_i \le 60$$$; for all $$$1 \le j \le M$$$, $$$h_j \le 60$$$.
  • Subtask 4 (42 points): No additional constraints.
Examples
Input
3
1 1 1
011
101
110
4
1 1 1 1
0100
1010
0101
0010
Output
INF
Input
3
1 2 2
010
101
010
4
1 2 3 2
0100
1010
0101
0010
Output
2
Input
2
1 3
01
10
3
1 3 3
011
101
110
Output
3