Prologin, the French National Computer Science Contest

Énoncé¶

Joseph Marchand a souvent des mots incongrus sur le bout de la langue, il aimerait bien savoir si ces mots sont de réelles inventions (potentiellement brevetables) ou simplement un manque de vocabulaire de sa part.

Pour l'aider, considérons un dictionnaire (une liste de n mots triés par ordre alphabétique), permettant de dire si le mot donné en entrée est un néologisme.

Un néologisme (du grec ancien νέος/néos, « nouveau », et λόγος/lógos, « parole ») est un mot nouveau : il n'existe pas dans le dictionnaire.

Rechercher si le mot existe dans le dictionnaire :

Entrée¶

Sur la première ligne, m, la taille du mot
Sur la seconde ligne, mot, le mot à tester
Sur la troisième ligne, un entier n, la taille du dictionnaire
Sur les 2N lignes suivantes, un tableau dictionnaire[n] :
- sur la ligne 2i : la taille du mot i
- sur la ligne 2i+1 : le mot i

Sortie¶

Sur la première ligne, 1 si "mot" est un néologisme, 0 sinon

Contraintes¶

1 <= N <= 400000

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

9
raspberry
9
6
alesia
4
argh
5
babar
4
blue
6
crayon
7
epsilon
7
jupiter
5
nuage
8
mstrkrft

Sample output