G. GPT in Fury
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have discovered that the scroll in your hands contains the legendary interview of Versteppen with Pó de Pá, with the help of ChatGPT. However, the data from your interaction with the AI has gone to OpenAI's servers, and they do not want you to acquire the burst of knowledge from the interview. Therefore, the next time you request the transcription of the scroll, ChatGPT will choose some words from the text and encrypt them, replacing all the letters of the chosen words with random letters.

For example, if a part of the text says "tipo assim tamo competindo", ChatGPT might say that the transcription is "tipo lkopn zyre competindo", encrypting the second and third words and replacing their letters with random characters.

When you request a new transcription (since you forgot to save the previous one), you notice that something is strange, but you are not sure which words were faithfully transcribed and which had their characters replaced. Your task is, given the transcription, to identify which words were encrypted by ChatGPT. Since nobody is perfect, your efforts will be considered acceptable if you can identify at least 70% of the words.

Note: Pay attention to the input and output format of the problem, as well as the notes at the end of the statement.

Input

The input consists of a single line with 7502 words, containing the interview in question, with potentially encrypted words.

To make reading easier, the original text was transcribed to only contain characters from a to z, normalizing the text so that it does not contain uppercase letters, accents, or numbers. For example, if a part of the original text was "Mas você já tá 300 por hora meu Deus do Céu" and none of the words in this part were encrypted by ChatGPT, this part would appear as "mas voce ja ta trezentos por hora meu deus do ceu".

If a word was encrypted by ChatGPT, it is guaranteed that all its characters will be generated randomly following a uniform distribution, that is, every character has the same chance of appearing. If a word was not encrypted, all its characters will appear as in the original transcription.

There will be $$$10$$$ test cases. In all of them, the original text is the same, and the only change will be the words that ChatGPT chooses to encrypt and the seed of the random generator used to generate the random characters.

Output

Print a single line with 7502 numbers separated by spaces. If you think the $$$i$$$-th word was encrypted by ChatGPT, the $$$i$$$-th number should be $$$1$$$. Otherwise, it should be $$$0$$$. If your solution correctly identifies whether the word was encrypted or not at least $$$70\%$$$ of the time, it will be accepted.

For technical reasons, you must flush the standard output after printing your solution.

In python, this can be done by importing the sys library and using the command sys.stdout.flush().

In C++, this can be done via cout « flush;

In C, this can be done via fflush(stdout);

Note

A snippet of the interview containing $$$403$$$ words will be provided at this link: https://pastebin.com/SFZnYeW8. Note that the interview is entirely in portuguese.

You can use this snippet to test your code before submitting, as well as to get an idea of the nature of the text.