SUBSN - Subsequence

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example “abd” is a subsequence of “abcdef”. - Wikipedia.

Your task in this problem is to decide if a given string is a subsequence of another string or not?

Easy?

Input

The first line of input will be the number of test cases. Each test case will start with a line contains a string S, S will have letters from 'a' to 'z' and the length of S ≤ 100,000. This line will be followed by a number Q which is the number of queries you have to answer for the given string S, 1 ≤ Q ≤ 1000. Each of the next Q lines will contain a string T, T will have letter from 'a' to 'z' and the length of T ≤ 200. For each T you have to decide if T is a subsequence of S or not.

Output

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines will have either “YES” or “NO” if the cross-ponding T is a subsequence of S or not respectively.

Example

Input:
1
abcdef
3
abd
adb
af

Output:
Case 1:
YES
NO
YES

Editors note:
Strings in the input can be empty. Read data carefully to avoid issues. There should be no extra whitespaces of course except '\n'.


Added by:hossamyosef
Date:2013-05-13
Time limit:0.408s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:FCIS/ASU Local Contest 2013

hide comments
2024-06-12 05:39:48
Example read on cpp
str ln;
lli t;
getline(cin, ln);
t=stoi(ln);
wl(t>0){
str s1;getline(cin, s1);
// ........
getline(cin, ln);
lli q;
q=stoi(ln);
cout<<"Case "<<x<<":"<<endl;
f(i,0,q){
str st;getline(cin, st);
//......
2019-10-23 08:12:48
can some body explain why getline works for this question while cin not.. and i have to add one extra getline before?
2019-02-03 10:22:29
easy dp
2017-06-26 13:24:19 Rajat Saxena
please anyone give a link of working solution to this problem. It will be of great help as it will demonstrate taking empty strings as input in c++. Thanks!
2016-09-14 10:26:37
Stupid input format
2016-06-15 05:58:58 Bhuvnesh Jain
why is time limit so strict?
2016-03-17 12:25:08
stupid input format
erase that plz
2015-11-30 21:26:42 Rishav Goyal
stupid input format. author could remove this garbage. spent 40 minutes to remove wA for that.

Last edit: 2015-11-30 21:27:24
2014-10-29 14:25:18 rohith
For an empty string the output should be "YES".Correct me if i am wrong :)
2014-09-14 06:13:30 Apurv
what wud the O/p for an empty string?? please help
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.