rcabreu

int C[N];
 
int read(int i) {
    int sum = 0;
    while (i > 0) {
        sum += C[i];
        i -= (i & -i);
    }
    return sum;
}

rcabreu

class SegmentTree {
private:
    vector<int> st;
    vector<int> a;
    int n;
    int left(int p) { return (p << 1); }
    int right(int p) { return (p << 1) + 1; }

    void initialize(int p, int L, int R) {
        if (L == R)

rcabreu

struct node {
    node *children[26];
    int words;
    int prefixes;
};

struct trie {
    node *root;
};

rcabreu

#define DIM 2 // default to 2. Set value according to problem.
struct matrix{
  ll a[DIM][DIM];
	
	// constructor. Make an empty array.
	matrix() {
		memset(a, 0, sizeof(ll) * DIM * DIM);
	}

rcabreu

vector<int> kmp(string str, string pattern) {
    vector<int> T(pattern.size() + 1, -1);
    vector<int> matches;
        if(pattern.size() == 0) {
            matches.push_back(0);
            return matches;
        }
        for(int i = 1; i <= pattern.size(); i++) {
                int pos = T[i - 1];
                while(pos != -1 && pattern[pos] != pattern[i - 1]) pos = T[pos];

rcabreu

#define MAXN 1000
#define INF 1000000009
struct node {
    int     id; 
    int     d;  
    int     pos; 
    int     p;  

    node(){}
    node(int _id, int _d, int _pos, int _p) {

rcabreu

const int MAXN = 1 << 21;
string S;
int N, gap;
int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

bool sufCmp(int i, int j){
    if (pos[i] != pos[j])
         return pos[i] < pos[j];
   i += gap;

rcabreu

ll fast_expo(ll base, ll expt) {
    if (expt == 0) return 1LL;
    if (expt == 1) return base;
    ll ans = fast_expo(base, expt / 2);
    ans = (ans + MOD) % MOD;
    ans = (ans * ans + MOD) % MOD;
    if (expt & 1LL) ans = (ans * base + MOD) % MOD;
    return ans;
}

rcabreu

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>

rcabreu

class UnionFind {
private:
  vector<int> p;
  vector<int> rank;

public:
    UnionFind(int n) {
        rank.assign(n, 0);
	p.resize(n);
	for (int i = 0; i < n; ++i) p[i] = i;