/*
* Olimpiada Națională de Informatică, Pitești 2014
*
* © 2014 Bogdan Cristian Tătăroiu
*/
#include <cstdio>
#include <cassert>
#include <list>
#include <string>
#include <vector>
#include <cstring>
const int MAXL = 70000;
const int MAXQ = 100000;
const int MAXC = 500000;
const int REPTR = 1000;
using namespace std;
int L, C, Q, Lptr;
char initStr[MAXL + 1];
vector<int> lens;
vector<string> words;
int aib[MAXL + 3];
list<char> str;
vector<list<char> :: iterator> ptrs;
/*
int trieLeft[MAXC][26], tLeftCnt = 0;
int trieRight[MAXC][26], tRightCnt = 0;
*/
inline void add(int poz, int val) {
for (poz += 2; poz < MAXL + 3; poz += (poz ^ (poz - 1)) & poz) {
aib[poz] += val;
}
}
inline int query(int poz) {
int val = 0;
for (poz += 2; poz; poz &= (poz - 1)) {
val += aib[poz];
}
return val;
}
/*
inline int add_word(char word[]) {
int node = 0, len = 0;
char *p;
for (p = word; *p; p++, len++) {
if (trieLeft[node][*p - 'a'] == -1) {
tLeftCnt += 1;
trieLeft[node][*p - 'a'] = tLeftCnt;
}
node = trieLeft[node][*p - 'a'];
}
node = 0;
for (p--; p != word; p--) {
if (trieRight[node][*p - 'a'] == -1) {
tRightCnt += 1;
trieRight[node][*p - 'a'] = tRightCnt;
}
node = trieRight[node][*p - 'a'];
}
return len;
}
*/
inline pair<int, int> findPtrPoz(int poz) {
// argmax_{ptrPoz} (ptrPoz + sum_0^{ptrPoz - 1} cnt[i] <= poz)
// argmax_{ptrPoz} (ptrPoz + aib(ptrPoz - 1) <= poz)
int ptrPoz = 0, step = 1 << 16;
int curSum = 0;
for (; step; step >>= 1) {
if (ptrPoz + step - 1 < Lptr &&
(ptrPoz + step - 1) + (curSum + aib[ptrPoz + step]) <= poz) {
ptrPoz += step;
curSum += aib[ptrPoz];
}
}
/*
for (; step; step >>= 1) {
if (ptrPoz + step - 1 < Lptr &&
ptrPoz + step - 1 + query(ptrPoz + step - 2) <= poz) {
ptrPoz += step;
}
}
int curSum = query(ptrPoz - 2);
*/
return make_pair(ptrPoz - 1, curSum);
}
list<char> :: iterator walk(int ptr_poz, int between, int in_chain) {
list<char> :: iterator it;
if (in_chain <= between - in_chain + 1 || ptr_poz + 1 == Lptr) {
it = ptrs[ptr_poz];
for (int i = 0; i < in_chain; i++) {
it++;
}
} else {
it = ptrs[ptr_poz + 1];
for (int i = 0; i < between - in_chain + 1; i++) {
it--;
}
}
return it;
}
int main() {
assert(freopen("sir3.in", "rt", stdin));
//assert(freopen("in", "rt", stdin));
#ifndef DEBUG
assert(freopen("sir3.out", "wt", stdout));
#endif
assert(scanf(" %s", initStr) == 1);
for (L = 0; initStr[L]; L++) {
str.push_back(initStr[L]);
ptrs.push_back(str.end());
ptrs.back()--;
}
Lptr = L;
/*
memset(trieLeft, -1, sizeof(trieLeft));
memset(trieRight, -1, sizeof(trieRight));
*/
assert(scanf("%d", &C) == 1);
assert(1 <= C && C <= MAXC);
lens.reserve(C);
words.reserve(C);
for (int i = 0; i < C; i++) {
assert(scanf(" %s", initStr) == 1);
words.push_back(initStr);
lens.push_back(words.back().size());
}
assert(scanf("%d", &Q) == 1);
assert(1 <= Q && Q <= MAXQ);
int last_ans = 0;
int rePtr = REPTR;
int aa, bb;
// Q = 430;
for (int i = 0; i < Q; i++) {
rePtr -= 1;
if (rePtr == 0) {
rePtr = REPTR;
ptrs.clear();
for (list<char> :: iterator it = str.begin();
it != str.end(); it++) {
ptrs.push_back(it);
}
Lptr = L;
memset(aib, 0, sizeof(aib));
}
int type, poz;
assert(scanf("%d %d", &type, &poz) == 2);
assert(type == 0 || type == 1);
if (type == 0) {
char c;
assert(scanf(" %c", &c) == 1);
assert(scanf("%d %d", &aa, &bb) == 2);
if(last_ans == 0) poz ^= aa;
else poz ^= bb;
assert(1 <= poz && poz <= L + 1);
poz -= 1;
// assert('a' <= c && c <= 'z');
pair<int, int> pp = findPtrPoz(poz);
int ptr_poz = pp.first;
int cur_sum = pp.second;
/*
assert(ptr_poz + query(ptr_poz - 1) <= poz);
assert(ptr_poz + 1 >= Lptr ||
ptr_poz + 1 + query(ptr_poz) > poz);
assert(cur_sum == query(ptr_poz - 1));
*/
int between = query(ptr_poz) - cur_sum;
int in_chain = poz - (ptr_poz + cur_sum);
// printf("\tadd %d %c\n", poz, c);
list<char> :: iterator it = walk(ptr_poz, between, in_chain);
str.insert(it, c);
if (in_chain == 0) {
it--;
ptrs[ptr_poz] = it;
}
add(ptr_poz, 1);
L += 1;
} else {
int word;
assert(scanf("%d", &word) == 1);
assert(1 <= word && word <= C);
assert(scanf("%d %d", &aa, &bb) == 2);
if(last_ans == 0) poz ^= aa;
else poz ^= bb;
assert(1 <= poz && poz <= L);
poz -= 1;
word -= 1;
// printf("\tquery %d %d\n", poz, word);
if (poz + 1 < lens[word]) {
printf("0\n");
continue;
}
pair<int, int> pp[2] = {findPtrPoz(poz),
findPtrPoz(poz - lens[word] + 1)};
int ptr_poz[2] = {pp[0].first, pp[1].first};
int cur_sum[2] = {pp[0].second, pp[1].second};
/*
assert(cur_sum[0] == query(ptr_poz[0] - 1));
assert(cur_sum[1] == query(ptr_poz[1] - 1));
assert(ptr_poz[0] + query(ptr_poz[0] - 1) <= poz);
assert(ptr_poz[0] + 1 + query(ptr_poz[0]) > poz);
assert(cur_sum[0] == query(ptr_poz[0] - 1));
assert(ptr_poz[1] + query(ptr_poz[1] - 1) <= poz - lens[word] + 1);
assert(ptr_poz[1] + 1 + query(ptr_poz[1]) > poz - lens[word] + 1);
assert(cur_sum[1] == query(ptr_poz[1] - 1));
*/
int between[2] = {query(ptr_poz[0]) - cur_sum[0],
query(ptr_poz[1]) - cur_sum[1]};
int in_chain[2] = {poz - (ptr_poz[0] + cur_sum[0]),
poz - lens[word] + 1 - (ptr_poz[1] + cur_sum[1])};
int cst[2] = {min(in_chain[0], between[0] - in_chain[0] + 1),
min(in_chain[1], between[1] - in_chain[1] + 1)};
/*
printf("\tptr_poz %d %d\n\tcur_sum %d %d\n",
ptr_poz[0], ptr_poz[1], cur_sum[0], cur_sum[1]);
printf("\tbetween %d %d\n\tin_chain %d %d\n",
between[0], between[1], in_chain[0], in_chain[1]);
printf("\tcst[0] = %d cst[1] = %d\n", cst[0], cst[1]);
*/
bool match;
if (cst[0] < cst[1]) {
match = 1;
list<char> :: iterator it = \
walk(ptr_poz[0], between[0], in_chain[0]);
string :: reverse_iterator sit;
for (sit = words[word].rbegin();
sit != words[word].rend() && match; sit++) {
// printf("\t\t%c %c\n", *it, *sit);
match = *it == *sit;
it--;
}
} else {
match = 1;
list<char> :: iterator it = \
walk(ptr_poz[1], between[1], in_chain[1]);
string :: iterator sit;
for (sit = words[word].begin();
sit != words[word].end() && match; sit++) {
// printf("\t\t%c %c\n", *it, *sit);
match = *it == *sit;
it++;
}
}
last_ans = match ? 1 : 0;
printf("%d\n", last_ans);
}
/*
for (list<char> :: iterator it = str.begin(); it != str.end(); it++) {
printf("%c", *it);
}
printf("\n");
*/
}
return 0;
}
Spatarel Dan-Constantin
spatarel
