heno239

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>

heno239

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>

heno239

struct online_Z_algorithm {
private:
	string s;
	vector<int> a;
	queue<int> cur;
	vector<bool> deleted;

	vector<vector<int>> delete_memo;
public:
	online_Z_algorithm() { delete_memo.push_back({}); };

heno239

struct online_Z_algorithm {
private:
	string s;
	vector<int> a;
	set<int> cur;

	vector<vector<int>> delete_memo;
public:
	online_Z_algorithm() { delete_memo.push_back({}); };
	void del(int loc, int len) {

heno239

void output_for_gcj(vector<string> &ans) {
	int n = ans.size();
	rep1(i, n) {
		cout << "Case " << i << ": " << ans[i-1] << endl;
	}
}

heno239

//

heno239

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;

heno239

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)

//数列aがあったとき、数b,l,rに対して、min{a[i]^b}(l<=i<r)を返すことのできるtri木

//bitの最大数(a[i]<2^30なら30)
const int digits = 30;
struct Node {

heno239

const int intmax = 2147483647;
struct SegT {
private:
	int n; vector<int> node;
public:
	SegT(int sz) {
		n = 1;
		while (n < sz)n <<= 1;
		//nodeの初期化
		node.resize(2 * n - 1, intmax);