ADAJOBS - Ada and Jobs

As you might already know, Ada the Ladybug has a huge TODO-list. Sometimes she inserts a new job into her TODO-list and sometimes she is wondering whether there is a job (in her TODO-list), which she wants to do now. She doesn't require the whole job to be there, perhaps just a part of it.

Can you create a program which would serve her? That means it either inserts a new job into her TODO-list or answers whether there exists a word (in her TODO-list) which is a substring of given word.


The first line of input containts Q, the number of queries.

The next Q lines contains a number 0 ≤ t ≤ 1 and nonempty string s. If t is equal to 0 then it is inserion query, otherwise it is question query. s consists of lowercase characters only.

The sum of lengths of queries of both types doesn't exceed 106 (that means the total sum of lengths of strings will be at most 2*106)


For each query of type 1, print either YES, if there is already a substring in the TODO-list and NO otherwise.

Example Input

0 cat
1 dogville
0 dog
1 dogville
1 gooutwithcat
1 gooutwithcrocodile
1 fancyconcatenation
0 crocodile
1 lacoste
1 gooutwithcrocodile
1 catalanreferendum
1 rocodile

Example Output


hide comments
morass: 2018-06-28 14:41:55

@rishabh1322: Good day to you,

Well I agree the "job" is there on multiple places which might lead to confuson. Here we ask whether there is a whole word which is substring of the query.

rishabh1322: 2018-04-24 11:17:21

0 crocodile
1 gooutwithcrocodile
1 rocodile
can you explain these cases

according to problem rocodile should print "YES"

Last edit: 2018-04-24 11:18:17
Mottakin Chowdhury: 2018-04-16 12:15:21


Last edit: 2018-04-16 16:39:18
morass: 2018-03-30 12:25:42

@Tanzir Islam: You were right, than you! I modified the statement!

Tanzir Islam: 2018-03-10 16:42:38

@morass Can you please check if this constraint stated in the input section " All newly added jobs will be distinct." correct? I got a WA because of this issue and fixed it. Then I submitted a code which checks if the same string has been given as job before and asserts false in that case. The code gets RTE. So I think there are strings in your input file which are not distinct and given as jobs.

morass: 2018-02-18 12:33:25

@amanvirat: Good day to you. Well sadly it isn't near required complexity. The part where you are printing is at least O(multiplocation of lengths of patterns and texts) :'(

amanvirat: 2018-02-16 19:25:19

@morass can you tell why this 21179409 give TLE.

julkas: 2018-01-04 15:10:32

@morass Thank you. It was my bug.

Last edit: 2018-01-04 15:10:48
morass: 2018-01-04 14:16:42

@julkas: Good day to you and happy new year. Is there something particular I shall investigate? The test-case your RTE on seems to have correct number of lines, with [0,1] digit and nonempty sequence of lowercase characters, whose sum is also low enough.

julkas: 2018-01-03 15:41:47

@morass Can you check input format, please.
My best regards and Happy New Year!

Added by:Morass
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)