NPC2015A - Eefun Guessing Words

Eefun is currently learning to read. His way of learning  is unique, by trying to make every possible substring from a given string. However, when the string becomes longer, he can no longer remember all the substring. His friends want to test Eefun's skill by asking questions, given a string S, is there any substring that begins with letter X and ends with letter Y? According to Eefun, each substring contains at least 2 letters. As the given string S is pretty big, Eefun need your help to answer his friend's questions

Input

First line of input contain a single string S which was given by his friends.
Second line contain a number N, the number of questions that Eefun's friends ask.
Next N lines each consists of 2 characters, X and Y

Output

For each questions, output a single string "YA" if the substring exists, or "TIDAK" otherwise
(YA means yes and TIDAK means no in Indonesian) 

Example

Input:
HALO
4
H O
L O
A O
O L 
Output:
YA
YA
YA
TIDAK 

Constraints:

  • 'A' ≤ X,Y ≤ 'Z'
  • 1 ≤ |S| ≤ 1.000.000
  • 1 ≤ N ≤ 1.000.000

Added by:Louis Arianto
Date:2015-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015

hide comments
2024-08-31 16:50:42
if you are using cpp cin and cout for input and output and you still have tle problems... try using scanf and printf (i had this problem)
2017-01-11 13:32:36 prakash
simple one but time limit is too strict o(q)+o(|s|)+fast i/o got AC
2017-01-10 14:32:46
sImple one AC in 1 go:-)
2016-06-27 14:52:35
My approach is O(N + |S|) and I have checked with all the possible inputs I can think of and it runs fine locally. Cannot see why I am getting a WA.
Edit: AC with completely different approach.

Last edit: 2016-06-27 17:26:43
2016-03-31 17:27:31 Alexey Merejine
I have WS on submission 16641335.
Can you please tell me what's the test data where it fails? @leonspirit? Thanks!
2015-12-04 16:38:56 Filip Sollar
use faster I/O got tle because of that test case very strong
2015-10-28 03:35:03 Bhargav Golla
Could you suggest what might be wrong with O(Nlog(|S|)) approach I did in submission 15486818? I am getting TLE, and I think we need at least log |S| time to answer each query.
2015-10-19 21:05:18 rahul_verma
Give me some more test cases !!
2015-10-18 15:12:16 Arianto Wibowo
@mehmetin Thanks. Rejudged :)
2015-10-18 14:24:42 mehmetin
I think the input is broken

Last edit: 2015-10-18 14:36:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.