// utils for gens
// by Vasilevskiy Boris

#define _CRT_SECURE_NO_DEPRECATE
#define _USE_MATH_DEFINES
#pragma comment (linker, "/STACK:30000000")

#include <iostream>
#include <algorithm>
#include <sstream>
#include <utility>
#include <string>
#include <memory>
#include <cassert>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <time.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(a, it) for (typeof((a).begin()) it = (a).begin(), it != (a).end(); ++it)
#define f0(a) memset((a), 0, sizeof(a))
#define ff(a) memset((a), -1, sizeof(a))
#define fv(a, value) tr(a, it) { (*it) = value; }
#define present(a, x) ((a).find(x) != (a).end())
#define sz(a) (int)((a).size())

typedef vector < int > VI;
typedef vector < VI > VII;
typedef pair < int, int > pii;
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()

typedef long long i64;

const int inf = (int)1e+9;
const double eps = (double)1e-9;

int rand32() {
    return (((int)rand() << 15) | ((int)rand() >> 1));
}

void gen_random_perm(VI &a, int len) {
    a.clear();
    a.reserve(len);
    a.pb(0);
    forn(i, len) {
        int j = rand32()%(i + 1);
        a.pb(a[j]);
        a[j] = i;
    }
}

char putc() {
    return rand()%26 + 'a';
}

char putC() {
    return rand()%26 + 'A';
}

char putchar() {
    if (rand()%2 == 0) 
        return rand()%26 + 'a';
    else
        return rand()%26 + 'A';
}

void randomize() {
    srand((unsigned)time(NULL));
}

int random(int left, int right) {
    return rand32()%(right - left + 1) + left;
}

int urand(int k) {
    return rand32()%(2*k + 1) - k;
}
