UAIC Competitive Programming

Problem 26: Subsequence Queries

Problem Statement: Given a string S and Q queries, each query consists of a string t. For every query determine whether t is a subsequence of S.

Input

The first line contains the string S. The second line contains an integer Q. Each of the next Q lines contains a query string t.

Output

For each query print "YES" if it is a subsequence of S, otherwise print "NO".

Examples


Input:
abacaba
2
aca
acb

Output:
YES
NO

Solution in C++


#include <iostream>
#include <string>
using namespace std;

bool isSubsequence(const string &s, const string &t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) j++;
        i++;
    }
    return j == t.size();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S; 
    getline(cin, S);
    int Q; cin >> Q;
    while(Q--) {
        string t; 
        cin >> t;
        cout << (isSubsequence(S, t) ? "YES" : "NO") << "\n";
    }
    return 0;
}