/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
0 と 1 からなる長さ M の文字列 S_1,S_2,\ldots,S_N が与えられます。
はじめ、黒板には S_1,S_2,\ldots,S_N が書かれています。
あなたは次の操作を 0 回以上行うことができます。
- 黒板に書かれている文字列から、同じ文字列を複数回選んでもよいものとして 3 つ選び、それぞれ A,B,C とする。次の条件を満たす長さ M の文字列 D を新たに黒板に書く。
- i=1,2,\ldots,M のそれぞれについて、A,B,C,D の i 文字目をそれぞれ A_i,B_i,C_i,D_i としたとき、D_i は A_i,B_i,C_i のうち少なくとも 2 つと等しい。
Q 個の文字列 T_1,T_2,\ldots,T_Q が与えられます。i=1,2,\ldots,Q のそれぞれについて、はじめの状態から操作を行うことで、T_i が黒板に書かれている状態にできるか判定してください。
制約
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- 1 \leq Q \leq 500
- S_i は
0と1からなる長さ M の文字列 (1 \leq i \leq N) - T_i は
0と1からなる長さ M の文字列 (1 \leq i \leq Q) - 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M Q S_1 S_2 \vdots S_N T_1 T_2 \vdots T_Q
出力
Q 行出力せよ。i 行目には、T_i が黒板に書かれている状態にできるなら Yes、できないなら No と出力せよ。
入力例 1
3 3 2 000 011 101 000 001
出力例 1
Yes Yes
T_1 ははじめから黒板に書かれています。
T_2 は 001 です。000、011、101 の 3 つを選ぶ操作を行うと、001 を黒板に新たに書くことができます。
入力例 2
2 1 2 0 0 0 1
出力例 2
Yes No
はじめに黒板に書かれている文字列はどちらも 0 であり、操作によって新たに書かれる文字列も 0 です。よって、1 が黒板に書かれている状態にできません。
Score : 700 points
Problem Statement
You are given length-M strings S_1,S_2,\ldots,S_N consisting of 0 and 1.
Initially, S_1,S_2,\ldots,S_N are written on the blackboard.
You can perform the following operation zero or more times.
- Choose three strings from those written on the blackboard, allowing the same string to be chosen multiple times, and call them A,B,C. Newly write on the blackboard a string D of length M satisfying the following condition:
- For each i=1,2,\ldots,M, letting A_i,B_i,C_i,D_i denote the i-th characters of A,B,C,D, respectively, D_i is equal to at least two of A_i,B_i,C_i.
You are given Q strings T_1,T_2,\ldots,T_Q. For each i=1,2,\ldots,Q, determine whether it is possible to make T_i be written on the blackboard by performing operations starting from the initial state.
Constraints
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- 1 \leq Q \leq 500
- S_i is a string of length M consisting of
0and1. (1 \leq i \leq N) - T_i is a string of length M consisting of
0and1. (1 \leq i \leq Q) - All input values are integers.
Input
The input is given from Standard Input in the following format:
N M Q S_1 S_2 \vdots S_N T_1 T_2 \vdots T_Q
Output
Output Q lines. The i-th line should contain Yes if T_i can be made to be written on the blackboard, and No otherwise.
Sample Input 1
3 3 2 000 011 101 000 001
Sample Output 1
Yes Yes
T_1 is written on the blackboard from the beginning.
T_2 is 001. If we perform the operation choosing the three strings 000, 011, 101, we can newly write 001 on the blackboard.
Sample Input 2
2 1 2 0 0 0 1
Sample Output 2
Yes No
The strings initially written on the blackboard are both 0, and the string newly written by the operation is also 0. Therefore, it is impossible to make 1 be written on the blackboard.