subprop

Se consideră o propoziţie formată din litere mici ale alfabetului englez şi eventual spaţii. Cuvintele sunt formate din litere mici şi sunt separate între ele prin unul sau mai multe spaţii.

Definim $putere$ asociată unui cuvânt $C_1 C_2 \dots C_k$ ca fiind un număr natural $v$ egal cu produsul puterilor de forma $P^i$, unde $P$ este poziţia în alfabet a literei $C_i$, $i=1,\dots,k$. Astfel cuvântului dab i se asociază $puterea$ egală cu $v = 4^1 \cdot 1^2 \cdot 2^3 = 4 \cdot 1 \cdot 8$, adică $v = 32$, pentru că litera d este pe poziția $4$, a pe poziția $1$ și b pe poziția $2$ în alfabet.

Definim $valoarea$ unui cuvânt $C_1 C_2 \dots C_k$ ca fiind numărul $nrd$ modulo $k$, unde $nrd$ este numărul de divizori ai lui $v$, $v$ fiind $puterea$ cuvântului $C$. $Valoarea$ cuvântului dab este $0$, pentru că $nrd=6$ (cei $12$ divizori ai lui $2048$ sunt: $1$, $2$, $4$, $8$, $16$, $32$), $k=3$ (cuvântul conţine $3$ litere) şi $6$ modulo $3 = 0$.

Definim $valoarea$ unei propoziţii ca fiind suma $valorilor$ cuvintelor existente în ea.

Prin $subpropoziție$ vom înțelege o propoziție nouă formată din unele cuvinte ale propoziției inițiale.

Cunoscând un șir de $N$ numere $x_1, x_2, \dots, x_N$ ne interesează să verificăm dacă pentru fiecare număr $x_i$, $i=1, 2, \dots, N$ există cel puțin o subpropoziție care să aibă valoarea $x_i$ ($1$ - există, $0$ - nu există).

Cerință

Pentru o propoziție ca cea din enunț și $N$ numere naturale se cere:

1. Valoarea primului cuvânt din propoziție
2. Un șir de $N$ valori $0$ sau $1$ ce corespunde existenței sau nu a unei supropoziții în propoziția dată cu valorile din șirul de numere $x_1$, $x_2$, \dots, $x_N$.

Date de intrare

Pe prima linie a fișierului de intrare subprop.in se găsește cerința $C$ ($1$ sau $2$), pe linia $2$ propoziția, pe lina $3$ numărul $N$, iar pe ultima linie cele $N$ numere $x_1$, $x_2$, $\dots$, $x_N$ separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire subprop.out se va găsi un număr corespunzător cerinței $1$, dacă $C = 1$, respectiv un șir de $N$ cifre $0$ sau $1$ separete prin câte un spațiu corespunzător cerinței $2$, dacă $C = 2$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$;
• propoziția are cel mult $100 \ 000$ de caractere;
• o propoziție are cel mult $10 \ 000$ cuvinte și un cuvânt are cel mult $1 \ 000$ de litere;
• $x_1$, $x_2$, $\dots$, $x_N$ sunt numere naturale $\leq 50 \ 000$;
• $A$ modulo $k$ reprezintă restul împărțirii lui $A$ la $k$;
• Pentru rezolvarea corectă a cerinței $1$ se vor acorda $20$ de puncte.
• Pentru rezolvarea corectă a cerinței $2$ se vor acorda $80$ de puncte.

Exemplul 1

subprop.in

1
dab ac dacaa
3
2 3 1

subprop.out

0

Explicație

$C = 1$. Valoarea primului cuvânt dab este $0$.

Exemplul 2

subprop.in

2
dab ac dacaa
2
3 5 

subprop.out

1 0

Explicație

$C = 2$. Valorile cuvintelor dab, ac și dacaa sunt $0$, $1$, respectiv $2$. O subpropoziție cu valoarea $3$ este formată din cuvintele ac și dacaa. Nu există subpropoziție cu valoarea $5$.