Thiago4532

#include <bits/stdc++.h>

using namespace std;
struct node{
    int v, w;
    node *l, *r;
    node(){
        l = NULL;
        r = NULL;
        v = 0;

Thiago4532

#include <bits/stdc++.h>
#define gc getchar
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;

inline int scan(){
	int n=0, x=gc(), s=1;
	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;
	for(;x>='0'&&x<='9';x=gc()) n = 10*n + x - '0';

Thiago4532

// Thiago Mota
// Splay Tree Implementation

#include <iostream>
#include <vector>

using namespace std;

struct node{
	int val;

Thiago4532

// Game - IOI'13
// Complexidade: O(n* log n)
// Thiago Mota

%:include <bits/stdc++.h>
%:define gc getchar_unlocked
using namespace std;random_device rd;mt19937 gen(rd());typedef long long ll;const int INF = 0x3f3f3f3f;typedef pair<int, int> pii;int N, M;ll mdc(ll a, ll b) <% return (b==0?a:mdc(b, a%b)); ??>inline int scan()<%	int N=0, x=gc(), s=1;	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;	for(;x>='0'&&x<='9';x=gc()) N = (N<<3) + (N<<1) + x-'0';	return N;??>struct Node<%	ll v, gcd;	int w;	pii key, ini, fim;	Node *l, *r;	Node(pii key, ll v): key(key), v(v), ini(key), fim(key), w(gen()), gcd(v), l(0), r(0) <%  ??>??>;inline ll gcd(Node *t) <% return (t?t->gcd:0); ??>inline void update(Node*& t)<%	if(!t) return;	t->gcd = mdc(t->v, mdc(gcd(t->l), gcd(t->r)));	t->ini = (t->l ? t->l->ini : t->key);	t->fim = (t->r ? t->r->fim : t->key);??>void merge(Node*& t, Node *l, Node *r)<%	if(!l || !r) return void(t=(l?l:r));	if(l->w >= r->w)<%		merge(l->r, l->r, r);		t = l;	??>else<%		merge(r->l, l, r->l);		t = r;	??>	updat

Thiago4532

// Leftist Tree ( Leftist Heap )
// Thiago Mota

#include <bits/stdc++.h>

using namespace std;

struct node{
	int key, dist;
	node *l, *r;

Thiago4532

// Leftist Tree ( Leftist Heap )
// Thiago Mota

#include <bits/stdc++.h>

using namespace std;

template<typename type>
class lheap{
public:

Thiago4532

// Link/Cut Tree
// Thiago Mota

#include <bits/stdc++.h>

using namespace std;
bool debug;

struct node{
    node *l, *r, *p;

Thiago4532

// Segment Tree with Lazy Propagation
// Thiago Mota

#include <bits/stdc++.h>
#define L (seg<<1)
#define R (L|1)
#define meio ((ini+fim)>>1)

using namespace std;
const int maxn = 1e3 + 10;

Thiago4532

#include <bits/stdc++.h>

using namespace std;

struct node{
	int v, w;
	node *l, *r;

	node(int v_=0){
		v = v_;

Thiago4532

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxs = 400;
int n, q, k, vet[maxn], bloco[maxn], ans[maxn][maxs];
int block;

inline int ini(int b){
	return ((b-1)*block) + 1;
}