E - 暗号変換装置とパスワード認証 解説 /

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

配点 : 466 点

問題文

高橋君は、N 人のエージェントにパスワードを送信して認証を行おうとしています。

パスワードは、1 以上 K 以下の整数からなる長さ L の列 S = (S_1, S_2, \dots, S_L) です。

高橋君の手元にはかすれたメモがあり、長さ L の列 B = (B_1, B_2, \dots, B_L) として読み取れます。ここで、

  • B_j = 0 のとき、その位置の値は読み取れなかったことを意味し、S_j を 1 以上 K 以下の好きな整数に定めることができます。
  • B_j \neq 0 のとき、S_j = B_j でなければなりません。

高橋君は送信を始める前に、すべての未確定の位置を埋めてパスワード S を完成させます。各位置は独立に 1 以上 K 以下の整数を選べます（異なる位置に同じ値を使ってもかまいません）。一度完成させた S は、その後変更できません。

送信には 1 台の暗号変換装置を使います。この装置は変換規則として \{1, 2, \dots, K\} 上の置換 C = (C_1, C_2, \dots, C_K) を保持しています。はじめ、C は恒等置換、すなわちすべての x（1 \leq x \leq K）について C_x = x です。

高橋君はパスワードを完成させた後、N 人全員に、自分で決めた順番でちょうど 1 回ずつ送信を行います。あるエージェント i への送信では、以下の処理がこの順に行われます。

  1. 送信と認証判定：装置の現在の変換規則 C を用いて、パスワード S の各要素が暗号化されて送られます。具体的には、エージェント i が受信する列は (C_{S_1}, C_{S_2}, \dots, C_{S_L}) です。この列がエージェント i の持つ認証コード T_i = (T_{i,1}, T_{i,2}, \dots, T_{i,L}) と完全に一致した場合、エージェント i の認証は成功します。
  2. 変換規則の更新：認証の成否にかかわらず、エージェント i が持つ置換 A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,K}) を用いて、装置の変換規則が更新されます。新しい変換規則 C' は、すべての x（1 \leq x \leq K）について

C'_x = A_{i, C_x}

で定まります（すなわち、合成 A_i \circ C に置き換わります）。

高橋君は、パスワード S の完成のさせ方と、N 人への送信順の両方を自由に選べます。

これらを最適に選んだとき、認証が成功するエージェントの人数の最大値を求めてください。さらに、その最大値を達成できる完成済みのパスワード S のうち、辞書順で最小のものを求めてください。ここで「最大値を達成できる」とは、ある送信順が存在して、その送信順のもとで認証が成功するエージェントの人数が最大値に等しくなることを意味します。

長さ L の列 U と V について、U \neq V であるとき、最初に異なる位置を j として U_j < V_j ならば U は V より辞書順で小さいとします。

制約

  • 1 \leq N \leq 8
  • 1 \leq K \leq 8
  • 1 \leq L \leq 200
  • 0 \leq B_j \leq K（1 \leq j \leq L）
  • 1 \leq T_{i,j} \leq K（1 \leq i \leq N, 1 \leq j \leq L）
  • 1 \leq A_{i,k} \leq K（1 \leq i \leq N, 1 \leq k \leq K）
  • A_i は \{1, 2, \dots, K\} の置換である（1 から K までの各整数をちょうど 1 回ずつ含む）
  • 入力はすべて整数である

入力

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

N K L
B_1 B_2 \dots B_L
T_{1,1} T_{1,2} \dots T_{1,L}
A_{1,1} A_{1,2} \dots A_{1,K}
T_{2,1} T_{2,2} \dots T_{2,L}
A_{2,1} A_{2,2} \dots A_{2,K}
\vdots
T_{N,1} T_{N,2} \dots T_{N,L}
A_{N,1} A_{N,2} \dots A_{N,K}
  • 1 行目には、エージェントの人数 N、値の種類数 K、パスワードの長さ L がスペース区切りで与えられる。
  • 2 行目には、かすれたメモを表す列 B がスペース区切りで与えられる。
  • 各 i（1 \leq i \leq N）について、続く 2 行でエージェント i の情報が与えられる。
  • 2i + 1 行目には、エージェント i の認証コード T_i がスペース区切りで与えられる。
  • 2i + 2 行目には、エージェント i の持つ置換 A_i がスペース区切りで与えられる。

出力

1 行目に、認証が成功するエージェントの人数の最大値を整数で出力してください。

2 行目に、その最大値を達成できる完成済みのパスワード S のうち辞書順で最小のものを、L 個の整数としてスペース区切りで出力してください。

入力例 1

2 3 4
0 2 0 1
1 2 3 1
2 1 3
2 1 3 2
2 3 1

出力例 1

2
1 2 3 1

入力例 2

3 2 5
0 0 1 0 2
1 1 1 2 2
2 1
2 2 1 1 2
1 2
1 2 2 1 1
2 1

出力例 2

1
1 1 1 2 2

入力例 3

5 5 12
0 3 0 0 5 1 0 2 0 0 4 0
1 3 2 4 5 1 2 2 3 4 4 5
2 3 4 5 1
2 1 1 5 4 3 3 2 5 1 4 2
1 3 5 2 4
5 3 5 1 5 1 4 2 4 3 4 1
5 4 3 2 1
3 4 2 2 1 5 1 3 2 5 5 4
3 1 2 5 4
4 5 3 4 2 2 5 1 1 2 3 3
4 5 1 3 2

出力例 3

1
1 3 2 4 5 1 2 2 3 4 4 5

入力例 4

8 8 40
0 2 0 4 0 6 0 8 1 0 3 0 5 0 7 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 0 2 4 6 8 0 0
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 1
8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1
8 7 6 5 4 3 2 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8
2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7
4 1 2 3 8 5 6 7
5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4
5 6 7 8 1 2 3 4
1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5
2 1 4 3 6 5 8 7
7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8
3 4 1 2 7 8 5 6
3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 1 1 1 1 2 2 2 2 3 4 5 6 7 8 1 2
1 2 3 4 5 6 7 8

出力例 4

1
1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5

入力例 5

1 1 1
0
1
1

出力例 5

1
1

Score : 466 pts

Problem Statement

Takahashi is trying to authenticate by sending a password to N agents.

The password is a sequence of length L consisting of integers between 1 and K inclusive: S = (S_1, S_2, \dots, S_L).

Takahashi has a faded memo, which can be read as a sequence of length L: B = (B_1, B_2, \dots, B_L). Here,

  • If B_j = 0, it means the value at that position could not be read, and S_j can be set to any integer between 1 and K inclusive.
  • If B_j \neq 0, then S_j = B_j must hold.

Before starting the transmission, Takahashi fills in all undetermined positions to complete the password S. Each position can independently be assigned any integer between 1 and K inclusive (the same value may be used at different positions). Once completed, S cannot be changed afterwards.

For transmission, a single cipher device is used. This device holds a conversion rule as a permutation C = (C_1, C_2, \dots, C_K) on \{1, 2, \dots, K\}. Initially, C is the identity permutation, i.e., C_x = x for all x (1 \leq x \leq K).

After completing the password, Takahashi transmits it to all N agents exactly once each, in an order he chooses. When transmitting to agent i, the following operations are performed in this order:

  1. Transmission and authentication check: Using the device's current conversion rule C, each element of the password S is encrypted and sent. Specifically, the sequence received by agent i is (C_{S_1}, C_{S_2}, \dots, C_{S_L}). If this sequence exactly matches agent i's authentication code T_i = (T_{i,1}, T_{i,2}, \dots, T_{i,L}), then agent i's authentication succeeds.
  2. Conversion rule update: Regardless of whether authentication succeeded or not, the device's conversion rule is updated using agent i's permutation A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,K}). The new conversion rule C' is defined for all x (1 \leq x \leq K) by

C'_x = A_{i, C_x}

(i.e., it is replaced by the composition A_i \circ C).

Takahashi is free to choose both how to complete the password S and the order of transmission to the N agents.

Find the maximum number of agents whose authentication can succeed when both choices are made optimally. Furthermore, among all completed passwords S that achieve this maximum, find the lexicographically smallest one. Here, "achieves the maximum" means that there exists some transmission order under which the number of agents whose authentication succeeds equals the maximum.

For two sequences U and V of length L, if U \neq V, let j be the first position where they differ; then U is lexicographically smaller than V if U_j < V_j.

Constraints

  • 1 \leq N \leq 8
  • 1 \leq K \leq 8
  • 1 \leq L \leq 200
  • 0 \leq B_j \leq K (1 \leq j \leq L)
  • 1 \leq T_{i,j} \leq K (1 \leq i \leq N, 1 \leq j \leq L)
  • 1 \leq A_{i,k} \leq K (1 \leq i \leq N, 1 \leq k \leq K)
  • A_i is a permutation of \{1, 2, \dots, K\} (contains each integer from 1 to K exactly once)
  • All input values are integers

Input

Input is given from standard input in the following format.

N K L
B_1 B_2 \dots B_L
T_{1,1} T_{1,2} \dots T_{1,L}
A_{1,1} A_{1,2} \dots A_{1,K}
T_{2,1} T_{2,2} \dots T_{2,L}
A_{2,1} A_{2,2} \dots A_{2,K}
\vdots
T_{N,1} T_{N,2} \dots T_{N,L}
A_{N,1} A_{N,2} \dots A_{N,K}
  • The first line contains the number of agents N, the number of value types K, and the password length L, separated by spaces.
  • The second line contains the sequence B representing the faded memo, separated by spaces.
  • For each i (1 \leq i \leq N), the following two lines give information about agent i:
  • Line 2i + 1 contains agent i's authentication code T_i, separated by spaces.
  • Line 2i + 2 contains agent i's permutation A_i, separated by spaces.

Output

On the first line, output the maximum number of agents whose authentication succeeds, as an integer.

On the second line, output the lexicographically smallest completed password S that achieves this maximum, as L integers separated by spaces.

Sample Input 1

2 3 4
0 2 0 1
1 2 3 1
2 1 3
2 1 3 2
2 3 1

Sample Output 1

2
1 2 3 1

Sample Input 2

3 2 5
0 0 1 0 2
1 1 1 2 2
2 1
2 2 1 1 2
1 2
1 2 2 1 1
2 1

Sample Output 2

1
1 1 1 2 2

Sample Input 3

5 5 12
0 3 0 0 5 1 0 2 0 0 4 0
1 3 2 4 5 1 2 2 3 4 4 5
2 3 4 5 1
2 1 1 5 4 3 3 2 5 1 4 2
1 3 5 2 4
5 3 5 1 5 1 4 2 4 3 4 1
5 4 3 2 1
3 4 2 2 1 5 1 3 2 5 5 4
3 1 2 5 4
4 5 3 4 2 2 5 1 1 2 3 3
4 5 1 3 2

Sample Output 3

1
1 3 2 4 5 1 2 2 3 4 4 5

Sample Input 4

8 8 40
0 2 0 4 0 6 0 8 1 0 3 0 5 0 7 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 0 2 4 6 8 0 0
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 1
8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1
8 7 6 5 4 3 2 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8
2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7 2 4 6 8 1 3 5 7
4 1 2 3 8 5 6 7
5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4 5 1 6 2 7 3 8 4
5 6 7 8 1 2 3 4
1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5
2 1 4 3 6 5 8 7
7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8
3 4 1 2 7 8 5 6
3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 1 1 1 1 2 2 2 2 3 4 5 6 7 8 1 2
1 2 3 4 5 6 7 8

Sample Output 4

1
1 2 1 4 2 6 3 8 1 4 3 6 5 8 7 2 4 1 6 2 8 3 1 4 2 5 3 6 4 7 5 8 6 1 2 4 6 8 7 5

Sample Input 5

1 1 1
0
1
1

Sample Output 5

1
1