const int N = 50010, M = 200010, S = 1000010;

int n, m, len, w[N], ans[M];
struct Query{
    int id, l, r;
}q[M];
int cnt[S];
int get(int x){
    return x / len;
}
bool cmp(const Query& a, const Query& b){
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}
void add(int x, int& res){
    if (!cnt[x]) res ++ ;
    cnt[x] ++ ;
}
void del(int x, int& res){
    cnt[x] -- ;
    if (!cnt[x]) res -- ;
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    scanf("%d", &m);
    len = max(1, (int)sqrt((double)n * n / m));
    for (int i = 0; i < m; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m, cmp);
    for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++ ){
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) add(w[ ++ i], res);
        while (i > r) del(w[i -- ], res);
        while (j < l) del(w[j ++ ], res);
        while (j > l) add(w[ -- j], res);
        ans[id] = res;
    }
    for (int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);
    return 0;
}
using namespace std;

const int N = 10010, S = 1000010;

int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct Query
{
    int id, l, r, t;
}q[N];
struct Modify
{
    int p, c;
}c[N];

int get(int x)
{
    return x / len;
}

bool cmp(const Query& a, const Query& b)
{
    int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl) return al < bl;
    if (ar != br) return ar < br;
    return a.t < b.t;
}

void add(int x, int& res)
{
    if (!cnt[x]) res ++ ;
    cnt[x] ++ ;
}

void del(int x, int& res)
{
    cnt[x] -- ;
    if (!cnt[x]) res -- ;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < m; i ++ )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q') mq ++, q[mq] = {mq, a, b, mc};
        else c[ ++ mc] = {a, b};
    }
    len = cbrt((double)n * max(1 , mc)) + 1;
    sort(q + 1, q + mq + 1, cmp);
    for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++ )
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        while (i < r) add(w[ ++ i], res);
        while (i > r) del(w[i -- ], res);
        while (j < l) del(w[j ++ ], res);
        while (j > l) add(w[ -- j], res);
        while (t < tm){
            t ++ ;
            if (c[t].p >= j && c[t].p <= i){
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
        }
        while (t > tm){
            if (c[t].p >= j && c[t].p <= i){
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
            t -- ;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= mq; i ++ ) printf("%d\n", ans[i]);
    return 0;
}
const int N = 1e5 + 10, M = 320;

typedef long long LL;

int n, m, len;
int w[N];
LL add[M], sum[M];

int find(int i)
{
    return i / len; 
}

void change(int l, int r, int d)
{
    if (find(l) == find(r)) while (l <= r) w[l] += d, sum[find(l ++ )] += d;
    else
    {
        int i = l, j = r;
        while (find(i) == find(l)) w[i] += d, sum[find(i ++ )] += d;
        while (find(j) == find(r)) w[j] += d, sum[find(j -- )] += d;

        for (int k = find(i); k <= find(j); k ++ ) sum[k] += len * d, add[k] += d;
    }
}

LL query(int l, int r)
{
    LL res = 0;
    if (find(l) == find(r)) while(l <= r) res += w[l] + add[find(l ++ )];
    else
    {
        int i = l, j = r;
        while (find(i) == find(l)) res += w[i] + add[find(i ++ )];
        while (find(j) == find(r)) res += w[j] + add[find(j -- )];

        for (int k = find(i); k <= find(j); k ++ ) res += sum[k];
    }
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);

    len = sqrt(n);
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &w[i]);
        sum[find(i)] += w[i];
    }
    int l, r, d;
    while (m -- )
    {
        char op[2];
        scanf("%s %d %d", op, &l, &r);

        if (op[0] == 'C')
        {
            scanf("%d", &d);
            change(l, r, d);
        }
        else printf("%lld\n", query(l, r));
    }
int n, m;
int h[N], e[M], ne[M], w[N], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Tree
{
    int l, r;
    LL add, sum;
}tr[N * 4];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    // TODO: 利用左右儿子信息维护当前节点的信息
}

void pushdown(int u)
{
    Tree &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += (left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (right.r - right.l + 1) * root.add;
        root.add = 0;
    }
    // TODO: 将懒标记下传
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, nw[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += d;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
        // TODO: 修改区间
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;  // TODO 需要补充返回值
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 0;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

void update_path(int u, int v, int d)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], d);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v); 
    update(1, id[v], id[u], d);
}

void update_tree(int u, int d)
{
    update(1, id[u], id[u] + sz[u] - 1, d);
}

LL query_path(int u, int v)
{
    LL res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    return res + query(1, id[v], id[u]);
}

LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}
struct Data
{
    int a, b, c, s, res;    // s 是单点的贡献(即所有重复数据)

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];  // 可以用权值线段树替换

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 归并排序
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    // 双指针统计区间合并时的贡献
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)  // 边界
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时贡献
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    // i 余下的仍然要加入树,以便于后面清空树状数组
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // 统计贡献,此时都是满足的
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);  // 清空树状数组
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}
int n, m, Q, new_n;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int dfn[N], low[N], cnt;
int s[N], stot[N], fu[N], fw[N], fe[N];
int fa[N][14], depth[N], d[N];
int A, B;

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void build_circle(int x, int y, int z)
{
    int sum = z;
    for (int k = y; k != x; k = fu[k])
    {
        s[k] = sum;
        sum += fw[k];
    }
    s[x] = stot[x] = sum;
    add(h2, x, ++ new_n, 0);
    for (int k = y; k != x; k = fu[k])
    {
        stot[k] = sum;
        add(h2, new_n, k, min(s[k], sum - s[k]));
    }
}

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ cnt;
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            fu[j] = u, fw[j] = w[i], fe[j] = i;  // fe[j]存储j由哪条边下来，这样可以处理重边问题。
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) add(h2, u, j, w[i]);
        }
        else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }
    for (int i = h1[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dfn[u] < dfn[j] && fe[j] != i)
            build_circle(u, j, w[i]);
    }
}

void dfs_lca(int u, int father)
{
    depth[u] = depth[father] + 1;
    fa[u][0] = father;
    for (int k = 1; k <= 13; k ++ )
        fa[u][k] = fa[fa[u][k - 1]][k - 1];
    for (int i = h2[u]; ~i; i = ne[i])
    {
        int j = e[i];
        d[j] = d[u] + w[i];
        dfs_lca(j, u);
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 13; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 13; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    A = a, B = b;
    return fa[a][0];
}
void init()
{
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

    g[1] = 1, g[3] = 3;
    for (int i = 4; i <= n; i ++ ) g[i] = g[i - 1] * i % m;
}
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            for (int k = 1; k <= i - j + 1; k ++ )
                f[i][j] = (f[i][j] + f[i - k][j - 1] * (LL)C[i - 1][k - 1] * g[k]) % m;

    LL res = g[n - 1], p = 1;
    for (int k = 2; k <= n; k ++ )
    {
        res += f[n][k] * p;
        p = p * n % m;
    }
bool dfs(int u, int c, int fg)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= fg) continue;
        if (color[j] == -1)
        {
            if (!dfs(j, !c, fg)) return false;
        }
        else if (color[j] == c) return false;
    }
    return true;
}

bool check(int mid)
{
    memset(color, -1, sizeof color);

    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1 && !dfs(i, 0, mid))
        {
            return false;
        }
    return true;
}
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if (i != (from ^ 1))
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top -- ];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 0; i < idx; i ++ )
        if (is_bridge[i])
            d[id[e[i]]] ++ ;

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ )
        if (d[i] == 1)
            cnt ++ ;

    printf("%d\n", (cnt + 1) / 2);

    return 0;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    if (u == root && h[u] == -1)
    {
        dcc_cnt ++ ;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j])
            {
                cnt ++ ;
                if (u != root || cnt > 1) cut[u] = true;
                ++ dcc_cnt;
                int y;
                do {
                    y = stk[top -- ];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}

int main()
{
    int T = 1;
    while (cin >> m, m)
    {
        for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(cut, 0, sizeof cut);

        while (m -- )
        {
            int a, b;
            cin >> a >> b;
            n = max(n, a), n = max(n, b);
            add(a, b), add(b, a);
        }

        for (root = 1; root <= n; root ++ )
            if (!dfn[root])
                tarjan(root);

        int res = 0;
        ULL num = 1;
        for (int i = 1; i <= dcc_cnt; i ++ )
        {
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j ++ )
                if (cut[dcc[i][j]])
                    cnt ++ ;

            if (cnt == 0)
            {
                if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else res ++ ;
            }
            else if (cnt == 1) res ++, num *= dcc[i].size() - 1;
        }
int spfa()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    int hh = 0, tt = 0;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;    // a++ -1 = 0
    q[tt ++ ] = 0;
    st[0] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return dist[N];
}
bool spfa()
{
    int hh = 0, tt = 0;
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0, sizeof dist);

    for (int i = 1; i <= n; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }

    while (hh != tt)
    {
        int t = q[hh ++ ];
        st[t] = false;

        if (hh == N) hh = 0;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                cnt[j] = cnt[t] + 1;
                dist[j] = dist[t] + w[i];
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++ ;
        } while (y != u);
    }
}
void topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (d[i] == 0)
        {
            q[ ++ tt] = i;
        }
    while (hh <= tt){
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if ( -- d[j] == 0){
                q[ ++ tt] = j;
            }
        }
    }
}
for (int i = n - 1; i >= 0; i -- )
{
    int j = q[i];
    f[j][j] = 1;
    for (int k = h[j]; ~k; k = ne[k])
        f[j] |= f[e[k]];
}

for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count());
int f()
{
    int res = 0;
    for (int i = 1; i < n; i ++ )
        if (q[i + 1] != q[i] + 1)
            res ++;
    return (res + 2) / 3;

}

bool check()
{
    for (int i = 1; i <= n; i ++ )
        if (i != q[i])
            return false;
    return true;
}

bool dfs(int dep, int max_dep)
{
    if (dep + f() > max_dep) return false;
    if (check()) return true;

    for (int l = 1; l <= n; l ++ )
        for (int r = l; r <= n; r ++ )
            for (int k = r + 1; k <= n; k ++ )
            {
                memcpy(w[dep], q, sizeof q);
                int x, y;
                for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[dep][x];
                for (x = l; x <= r; x ++, y ++ ) q[y] = w[dep][x];
                if (dfs(dep + 1, max_dep)) return true;
                memcpy(q, w[dep], sizeof q);
            }
    return false;
}

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth ++;

        if (depth == 5) puts("5 or more");
        else printf("%d\n", depth);
    }
}
bool cmp(LL a, LL b) {
    return a > b;
}

void dfs(int u, int s)
{
    if (u == k)
    {
        weights[cnt ++ ] = s;
        return;
    }

    if(s + g[u] <= w) dfs(u + 1, s + g[u]);
    dfs(u + 1, s);
}

void dfs2(LL u, LL s)
{
    if (u == n)
    {
        LL l = 0, r = cnt - 1;
        while (l < r)
        {
            LL mid = l + r + 1 >> 1;
            if(weights[mid] + s <= w) l = mid;
            else r = mid - 1;
        }
        if (weights[l] + s <= w) ans = max(ans, weights[l] + s);
        return;
    }
    if (g[u] + s <= w) dfs2(u + 1, s + g[u]);
    dfs2(u + 1, s);
}

int main()
{
    scanf("%lld %lld", &w, &n);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &g[i]);
    sort(g, g + n, cmp);
    k = n / 2 + 2;
    dfs(0, 0);
    sort(weights, weights + cnt);
    LL t = 1;
    for (int i = 1; i < cnt; i ++ )
        if(weights[i] != weights[i - 1])
        {
            weights[t ++ ] = weights[i];
        }
    cnt = t;
    dfs2(k, 0);
    printf("%lld", ans);
    return 0;
}
int R[N], H[N];     // R[] 记录的是每层的半径, H[] 记录的是每层的高度
int minv[N], mins[N];   // 
int ans = INF;

void dfs(int u, int v, int s)  // 当前开始搜索的层数 u , 当前总体积 v , 当前总外表面面积 s
{
    if (v + minv[u] > n) return;    // 当前累计的总体积 + 现在第 u 层最小可能体积 > 目标体积，剪枝
    if (s + mins[u] >= ans) return; // 当前累计的总表面积 + 现在第 u 层最小可能表面积 >= 答案，剪枝
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;
    // 公式推导
    if(!u) // 如果有答案的话
    {
        if(v == n) ans = s; // 体积相等就更新
        return;
    }


    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )
        for (int h = min(H[u + 1] - 1, (n- v) / r / r); h >= u; h -- )
        {
            int t = 0;
            if (u == m) t = r * r;

            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
            // 从下到上枚举
        }

    return;
}

int main()
{
    scanf("%d %d", &n, &m); // n 是体积, m 是层数

    for (int i = 1; i <= m; i ++ )  
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

    if (ans == INF) ans = 0;

    printf("%d", ans);

    return 0;

}
bool cmp(int a, int b) {
    return a > b;
}

bool dfs(int mx, int num, int u, int Len, int k)
{
    if (u > num) return true;
    if (Len == mx) return dfs(mx, num, u + 1, 0, 0);

    for (int i = k; i <= n; i ++ )
    {
        if (st[i]) continue;
        if (Len + stick[i] > mx) continue;

        st[i] = true;
        if (dfs(mx, num, u, Len + stick[i], i + 1)) return true;
        st[i] = false;

        if (!Len) return false;
        if (Len + stick[i] == mx) return false;
        int j = i;
        while (j <= n && stick[j] == stick[i]) j ++;
        i = j - 1;
    }
    return false;
}

int main()
{
    while (scanf("%d", &n) && n != 0)
    {
        int sum = 0;
        memset(st, false, sizeof st);
        memset(p, 0, sizeof p);
        for (int i = 1; i <= n; i ++ ) 
        {
            scanf("%d", &stick[i]);
            sum += stick[i];
        }
        sort(stick + 1, stick + n + 1, cmp);

        for (int i = 1, j = 1; i <= sum; i ++ )
            if (sum % i == 0 && i >= stick[1]) p[j ++ ] = i;

        for (int i = 1; p[i] != 0; i ++ ) 
            if (dfs(p[i], sum / p[i], 1, 0, 1)) 
            {
                printf("%d\n", p[i]);
                break;
            }
    }
    return 0;
}
int n;
string A, B;
string a[N], b[N];
//  参数：扩展的队列，到起点的距离，到终点的距离，规则，规则
//  满足条件的最小步数
int extend(queue<string>& q, map<string, int>&da, map<string, int>& db, string a[N], string b[N])
{
    int d = da[q.front()];
    while (q.size() && da[q.front()] == d)
    {
        string t = q.front();
        q.pop();

        for (int i = 0; i < n; i ++ )           // 扩展规则
            for (int j = 0; j < t.size(); j ++ )// 字符串长度
                if (t.substr(j, a[i].size()) == a[i])   // 可以开始扩展
                {
                    // 增添
                    string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
                    // 和 b串 相同，两个方向会师，返回最小步数
                    if (db.count(r)) return da[t] + db[r] + 1;
                    // 重复了
                    if (da.count(r)) continue;
                    // 多操作了 1 步
                    da[r] = da[t] + 1;
                    q.push(r);
                }
    }

    return 11;
}

int bfs()
{
    if (A == B) return 0;
    queue<string> qa, qb;
    map<string, int> da, db;

    qa.push(A); da[A] = 0;
    qb.push(B); db[B] = 0;

    int step = 0;
    while (qa.size() && qb.size())  
    {
        int t;
        // 双向广搜，哪个方向的队列的长度更小一些，空间更小一些，从该方向开始扩展，
        if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);

        if (t <= 10) return t;  // 找到了答案
        if ( ++ step == 10) return -1;
    }

    return -1;
}

int main()
{
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n ++ ;

    int t = bfs();
    if (t == -1) puts("NO ANSWER!");
    else cout << t << endl;

    return 0;
}
int bfs()
{
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);

    deque<PII> q;
    q.push_back({0, 0});
    d[0][0] = 0;

    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    char cs[] = "\\/\\/";

    while (q.size())
    {
        PII t = q.front();
        q.pop_front();

        int x = t.first, y = t.second;
        if (st[x][y]) continue;
        st[x][y] = true;

        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            int j = x + ix[i], k = y + iy[i];

            if (a >= 0 && a <= n && b >= 0 && b <= m)
            {
                int w = 0;
                if (g[j][k] != cs[i]) w = 1;
                if (d[a][b] > d[x][y] + w)
                {
                    d[a][b] = d[x][y] + w;     
                    if (w) q.push_back({a, b});
                    else q.push_front({a, b});
                }
            }
        }
    }
    if(d[n][m] == 0x3f3f3f3f) return -1;
    else return d[n][m];

}
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 400010, S = 51;

typedef pair<int, int> PII;

int T;
int n, m, K, P;
int ans;

int h[N], f[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N][S];

bool st[N], vis[N][S], flag = false;

void init()
{
    flag = false;
    idx = 0, ans = 0;
    memset(f, -1, sizeof f);
    memset(h, -1, sizeof h);
    memset(cnt, -1, sizeof cnt);
    memset(st, false, sizeof st);
}
void add(int h[], int a, int b, int c) 
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > heap;

    memset(dist, 0x3f, sizeof dist);
    dist[n] = 0;

    heap.push({0, n});
    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.second;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = f[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int s)
{
    if (vis[u][s]) 
    {
        flag = true;
        return 0;
    }
    if (cnt[u][s] != -1) return cnt[u][s];

    vis[u][s] = true;
    int &Cnt = cnt[u][s] = 0;
    for (int i = h[u]; i != -1; i = ne[i])
        if (!flag) {
            int v = e[i];
            int k = s - (dist[v] + w[i] - dist[u]);
            if (0 <= k && k <= K) Cnt = (Cnt + dfs(v, k)) % P;
        }
    if (flag) return 0;
    vis[u][s] = false;
    if (u == n && s == 0) Cnt = 1;
    return Cnt;
}

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        init();
        scanf("%d %d %d %d", &n, &m, &K, &P);
        while (m -- )
        {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            add(h, a, b, c), add(f, b, a, c);
        }
        dijkstra();

        for (int i = 0; i <= K; i ++ ) 
            if (!flag)
            {
                memset(vis, false, sizeof vis);
                ans = (ans + dfs(1, i)) % P;
            }
        if (flag) puts("-1");
        else printf("%d\n", ans);
    }
    return 0;
}
bool check(int l, int r, int d)
{
    return l <= d && d <= r;
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; 
}

int dijkstra(int down, int up)  // 求1号点到n号点的最短路距离
{
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;    // 从虚拟源点开始
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 0});  // 加入虚拟源点

    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();

        int ver = t.second;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i] && check(down, up, level[j])) // 判断出边是否满足
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    return dist[1];
}


int main()
{
    scanf("%d %d", &m, &n);

    memset(h, -1, sizeof h);
    int price, num;
    for (int i = 1; i <= n; i ++ )
    {
        int idx = i;
        scanf("%d %d %d", &price, &level[idx], &num);

        add(0, idx, price);

        for (int j = 1; j <= num; j ++ )
        {
            int b, c;
            scanf("%d %d", &b, &c);
            add(b, idx, c);
        }
    }

    // 枚举等级区间, 每次只和等级在这个区间内的人做交易
    int ans = 0x3f3f3f3f;
    for (int k = level[1] - m; k <= level[1]; k ++ )
    {
        ans = min(ans, dijkstra(k, k + m));
    }
    printf("%d", ans);
    return 0;
}
struct Smgment  // 用来存线段信息
{
   double x, y1, y2;
   int k;       // 区分它是该矩阵前面的线段还是后面的线段

   bool operator< (const Smgment &t)const
   {
       return x < t.x;
   }
}segm[N * 2];   //每个矩阵需要存两个线段

// 线段树的每个节点 保存的为线段, 0号点为y[0]到y[1], 以此类推
struct Smtree
{
   int l, r;
   int cnt;         // 记录这段区间出现了几次
   double len;      // 记录这段区间的长度;即线段长度
}seg[N * 8];        //由于线段二倍，所以8倍空间

vector<double> ys;     //用于离散化

int find(double y)  // 需要返回vector 中第一个 >= y 的数的下标
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int p)  // 由下往上传递信息
{
    if (seg[p].cnt) seg[p].len = ys[seg[p].r + 1] - ys[seg[p].l];   
    //表示整个区间都被覆盖，该段长度就为右端点 + 1后在ys中的值 - 左端点在ys中的值

    // 如果seg[u].cnt等于0其实有两种情况:
    // 1. 完全覆盖. 这种情况由modify的第一个if进入. 
    //    这时下面其实等价于把"由完整的l, r段贡献给len的部分清除掉", 
    //    而留下其他可能存在的子区间段对len的贡献
    // 2. 不完全覆盖, 这种情况由change的else最后一行进入. 
    //    表示区间并不是完全被覆盖，可能有部分被覆盖,所以要通过儿子的信息来更新
    else if (seg[p].l != seg[p].r)
    {
        seg[p].len = seg[p * 2].len + seg[p * 2 + 1].len;
    }
    else seg[p].len = 0;    // 表示为叶子节点且该线段没被覆盖，为无用线段，长度变为0
}

void build(int p, int l, int r)
{
    seg[p] = {l, r, 0, 0}; 
    if (l == r) return;

    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}
//表示从线段树中 l点 到 r点 的出现次数 + k
void change(int p, int l, int r, int k)
{
    if (seg[p].l >= l && r >= seg[p].r) // 该区间被完全覆盖
    {
        seg[p].cnt += k;    // 该区间出现次数 + k

        pushup(p);          // 更新该节点的len
        return;
    }
    int mid = seg[p].l + seg[p].r >> 1;
    if (l <= mid) change(p * 2, l, r, k);   // 左边存在点
    if (r > mid) change(p * 2 + 1, l, r, k);// 右边存在点

    pushup(p);  // 进行更新
}

signed main()
{
    int T = 1;
    while (scanf("%lld", &n))
    {
        if (n == 0) break;
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            segm[j ++ ] = {x1, y1, y2, 1}; // 前面的线段
            segm[j ++ ] = {x2, y1, y2, -1};// 后面的线段
            ys.push_back(y1), ys.push_back(y2); // y轴出现过哪些点
        }
        sort(segm, segm + n * 2);   // 线段按x排序

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )
        {
            //根节点的长度即为此时有效线段长度 ，再 * x轴长度即为面积
            if (i > 0) res += seg[1].len * (segm[i].x - segm[i - 1].x);

            change(1, find(segm[i].y1), find(segm[i].y2) - 1, segm[i].k);
        }

        printf("Test case #%lld\n", T ++ );
        printf("Total explored area: %.2lf\n\n", res);       
    }
    return 0;
}
int get(int x)
{
    if(x == fa[x]) return x;
    int root = get(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}

int main()
{
    scanf("%d", &t);
    for (int i = 0; i < N; i ++ ) sz[i] = 1, fa[i] = i;

    while (t -- ) {
        int x, y;
        scanf("%s %d %d", op, &x, &y);
        int a = get(x), b = get(y);
        if (op[0] == 'M')
        {
            if (a != b) {
                fa[a] = b;
                d[a] = sz[b], sz[b] += sz[a];
            }
        }
        else {
            if (a == b) printf("%d\n", max(0, abs(d[y] - d[x]) - 1));
            else puts("-1");
        }
    }
}
int n, m;
int f1[N] = {1, 1, 1};
int A[N][N] = 
{   {0, 1, 0},
    {1, 1, 1},
    {0, 0, 1}
};

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
            {
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
            }
    memcpy(c, temp, sizeof temp);
}
int main()
{
    scanf("%d%d", &n, &m);
    n --;
    while (n)
    {
        if (n & 1) mul(f1, f1, A);
        mul(A, A, A);
        n >>= 1;
    }
    printf("%d", f1[2] % m);
}
int n, mod;
int f[4] = {0, 1, 1, 0};
int X[4][4] = {
    {0, 1, 1, 0},
    {1, 1, 1, 0},
    {0, 0, 1, 1},
    {0, 0, 0, 1}
};

void mul1(int A[], int B[][4])
{
    int ans[4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
        {
            ans[i] += (A[j] * B[j][i]) % mod;
        }
    for (int i = 0; i < 4; i ++ )
        A[i] = ans[i];
}

void mul2(int A[][4], int B[][4])
{
    int ans[4][4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            for (int k = 0; k < 4; k ++ )
            {
                ans[i][j] += (A[i][k] * B[k][j]) % mod;
            }
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            A[i][j] = ans[i][j];
}

void qmi(int n)
{
    while (n)
    {
        if (n & 1) mul1(f, X);
        mul2(X, X);
        n >>= 1;
    }
}

signed main()
{
    scanf("%lld%lld", &n, &mod);
    qmi(n - 1);

    printf("%d", ((n * f[2] - f[3]) % mod + mod) % mod);
}
double f[N];

void add(int a, int b, int c)   // 逆推
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

double Exp(int u)
{
    if (f[u] >= 0) return f[u]; // 记忆化搜索

    f[u] = 0;                   // 搜过了
    for (int i = h[u]; i != -1; i = ne[i])  // 找到其所有的出边
    {
        int j = e[i];
        f[u] += (w[i] + Exp(j)) / d[u]; // 期望 = 路径长度 / 出边 
    }
    return f[u];
}

int main()
{
    scanf("%d %d", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 1, a, b, c; i <= m; i ++ )
    {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), d[a] ++;
    }

    memset(f, -1, sizeof f);
    printf("%.2lf", Exp(1));

    return 0;
}
double dp(int a,int b,int c,int d,int x,int y)
{
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    // 4个牌堆有的数量
    int as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);

    if (as >= A && bs >= B && cs >= C && ds >= D) return v = 0;
    // 目前四个牌堆已经共有sum个
    int sum = a + b + c + d + (x != 4) + (y != 4);
    // 总剩余
    sum = 54 - sum;
    if (sum <= 0) return v = INF;
    // 四种花色
    v = 1;//到下一层的各个节点的期望的和 Σp(j) for j in ne[i]
    if (a < 13) v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
    if (b < 13) v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
    if (c < 13) v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
    if (d < 13) v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
    // 小王
    if (x == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
        v += t;
    }
    // 大王
    if (y == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
        v += t;
    }

    return v;
}

int main()
{
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof f);

    double t = dp(0, 0, 0, 0, 4, 4);
    if (t > INF / 2) t = -1;

    printf("%.3lf\n", t);

    return 0;
}
inline void add(int u, int v)        // 加边函数。从点 u 向点 v 连一条有向边
{
    e[ ++ idx] = v;
    ne[idx] = h[u];
    h[u] = idx;
}

int SG(int u)
{
    if (~sg[u]) return sg[u];        // 如果当前 sg[u] 不是 -1，那么说明该点的 SG 函数值已经被计算过了，直接返回
    set<int> S;                      // 否则要建一个集合 S，存该点能到的所有点的 SG 函数值
    for (int i = h[u]; i; i = ne[i]) // 遍历点 u 能到达的所有点
        S.insert(SG(e[i]));          // 计算该点的 SG 函数值，并放入集合 S
    for (int i = 0; ; i ++ )         // 从 0 开始枚举所有非负整数
        if (!S.count(i))             // 如果该值没有在 S 中出现过
        {
            sg[u] = i;               // 那么将该值记录在 sg[u] 中并返回
            return i;
        }
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);   // 读入题目中 N, M, K
    for (int i = 0; i < m; i ++ )    // 读入 M 条边并建图
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    memset(sg, -1, sizeof sg);       // 先将 sg 数组中的所有值初始化成 -1，表示没有记录过
    while (k -- )                    // 读入 K 个棋子所在的点
    {
        int u;
        scanf("%d", &u);
        res ^= SG(u);
    }
    if (res) puts("win");            // 如果 res 不为 0，那么输出 win
    else    puts("lose");            // 否则输出 lose
    return 0;
}
   while(T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        // 长度
        for (int len = 1; len <= n; len ++ )
            //  左右端点i 右端点j
            for (int i = 1; i + len - 1 <= n; i ++ )
            {
                int j = i + len - 1;
                // 区间只有一个堆x 则左右取为x -> x [x] x
                // 只要先手取哪一堆 后手在另一堆取一样多的石子
                // 则只要先手取得这堆有,后手取得另一堆也一定有,
                // 直到先手取得那堆取完,后手把另一堆取完 先手必败
                if (len == 1) l[i][j] = r[i][j] = a[i];
                else
                {
                    int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
                    // 情况1
                    if (R == X) l[i][j] = 0;
                    // 情况2 情况4
                    else if (X < L && X < R || X > L && X > R) l[i][j] = X;
                    // 情况3.1 情况4.1
                    else if (L > R) l[i][j] = X - 1;
                    // 情况3.2 情况4.2
                    else l[i][j] = X + 1;

                    // 与上述情况对称的四种情况
                    L = l[i + 1][j], R = r[i + 1][j], X = a[i];
                    if (L == X) r[i][j] = 0;
                    else if (X < L && X < R || X > L && X > R) r[i][j] = X;
                    else if (R > L) r[i][j] = X - 1;
                    else r[i][j] = X + 1;
                }
            }

        if (n == 1) puts("1");
        else printf("%d\n", l[2][n] != a[1]);
    }
    return 0;
}
double a[N][N], b[N][N];

void gauss()
{
    // 转化成上三角矩阵
    for (int r = 1, c = 1; c <= n; c ++, r ++ )
    {
        // 找主元
        int t = r;
        for (int i = r + 1; i <= n; i ++ )
            if (fabs(b[i][c]) > fabs(b[t][c]))
                t = i;

        // 交换
        for (int i = c; i <= n + 1; i ++ ) swap(b[t][i], b[r][i]);
        // 归一化
        for (int i = n + 1; i >= c; i -- ) b[r][i] /= b[r][c];
        // 消
        for (int i = r + 1; i <= n; i ++ )
            for (int j = n + 1; j >= c; j -- )
                b[i][j] -= b[i][c] * b[r][j];
    }

    // 转化成对角矩阵
    for (int i = n; i > 1; i -- )
        for (int j = i - 1; j; j -- )
        {
            b[j][n + 1] -= b[i][n + 1] * b[j][i];
            b[j][i] = 0;
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n + 1; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%lf", &a[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            b[i][j] += 2 * (a[i][j] - a[0][j]);
            b[i][n + 1] += a[i][j] * a[i][j] - a[0][j] * a[0][j];
        }

    gauss();

    for (int i = 1; i <= n; i ++ ) printf("%.3lf ", b[i][n + 1]);
int a[N];
int f[N], q[N];

bool check(int mit)
{
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && q[hh] < i - mit) hh ++;
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[ ++ tt] = i;
    }
    if (q[hh] < n - mit + 1) hh ++; 
    return f[q[hh]] <= t;
}

int main()
{
    scanf("%d %d", &n, &t);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int l = 0, r = n;
    while (l < r)   // >=
    {
        int mid = l + r >> 1;
        if (check(mid + 1)) r = mid;    // mid 是空隔，mid + 1
        else l = mid + 1;
    }

    printf("%d", l);
}
int n;
int p[M], d[M], que[M];
LL sp[M], sd[M];
bool f[N];

LL g(int j)
{
    return sp[j] - sd[j];
}
LL h(int j)
{
    return sd[j - 2] - sp[j - 1];
}
LL get_val1(int i, int j)
{
    return sd[i - 1] - sp[i - 1] + g(j);
}
LL get_val2(int i, int j)
{
    return sp[i + n] - sd[i + n - 1] + h(j);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &p[i], &d[i]);
        p[i + n] = p[i];
        d[i + n] = d[i];
    }
    for (int i = 1; i <= n << 1; i ++ )
    {
        sd[i] = sd[i - 1] + d[i];
        sp[i] = sp[i - 1] + p[i];
    }

    int hh = 0, tt = -1;
    for (int i = 1; i <= n << 1; i ++ )
    {
        while (hh <= tt && i - que[hh] > n) hh ++ ;
        if (i > n)
            if (get_val1(i - n, que[hh]) >= 0)
                f[i - n] = true;
        while (hh <= tt && g(que[tt]) >= g(i)) tt -- ;
        que[ ++ tt] = i;
    }

    hh = 0, tt = -1;
    for (int i = n << 1; i; i -- )
    {
        while (hh <= tt && que[hh] - i > n) hh ++ ;
        if (i <= n)
            if (get_val2(i, que[hh]) >= 0)
                f[i] = true;
        while (hh <= tt && h(que[tt]) >= h(i)) tt -- ;
        que[ ++ tt] = i;
    }
    for (int i = 1; i <= n; i ++ )
        puts(f[i] ? "TAK" : "NIE");
    return 0;
}
int f[N][N];

int dp(int pos, int st, int op)
{
    if (!pos) return 1;
    if (!op && ~f[pos][st]) return f[pos][st];
    int res = 0, maxx = op ? a[pos] : 9;
    for (int i = 0; i <= maxx; i ++ )
        if (i != 4 && (st != 6 || i != 2))
            res += dp(pos - 1, st == -1 && !i ? -1 : i, op && i == a[pos]);
    return op && st == -1 ? res : f[pos][st] = res;
}
int calc(int x)
{
    memset(f, -1, sizeof f); al = 0;
    for ( ; x; x /= 10) a[ ++ al] = x % 10;
    return dp(al, -1, 1);
}
int main()
{
    while (cin >> l >> r, l || r)
    {
        cout << calc(r) - calc(l - 1) << endl;
    }
    return 0;
}
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]), a[i + n] = a[i];    // 环拆链
    }

    for (int len = 3; len <= n + 1; len ++ )    // 至少要三个合并
        for (int l = 1, r; r = l + len - 1, r <= n << 1; l ++ ) // 最后记得要合并首尾
        {
            for (int k = l + 1; k < r; k ++ )   // 决策
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            }
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ )  // 找最大值
    {
        int j = i + n;
        res = max(res, f[i][j]);
    }
void dfs(int u, int fa)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k <= j - 1; k ++ )
            {
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + w[i]);
            }
    }
}
int cmp(double x, double y)
{
    if (fabs(x - y) < eps) return 0;
    if (x > y) return 1;
    return -1;
}
for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);

memset(path, 0, sizeof path);
for (int i = 0; i < n; i ++ )
{
    path[i][i] = 1 << i;
    for (int j = 0; j < n; j ++ )
    {
        double x1 = q[i].x, y1 = q[i].y;
        double x2 = q[j].x, y2 = q[j].y;
        if (!cmp(x1, x2)) continue;
        double a = (y1 / x1 - y2 / x2) / (x1 - x2);
        double b = y1 / x1 - a * x1;
        if (cmp(a, 0) >= 0) continue;
        int state = 0;
        for (int k = 0; k < n; k ++ )
        {
            double x = q[k].x, y = q[k].y;
            if (!cmp(a * x * x + b * x, y)) state += 1 << k;
        }
        path[i][j] = state;
    }
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i + 1 < 1 << n; i ++ )
{
    int x = 0;
    for (int j = 0; j < n; j ++ )
    {
        if (!(i >> j & 1))
        {
            x = j;
            break;
        }
    }
    for (int j = 0; j < n; j ++ )
        f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
}
printf("%d\n", f[(1 << n) - 1]);
int vis[N], lev[N], d[N];
//vis : 已经访问过的点
//lev : 点距离初始点的距离
//d : 通过此点可以达到的点数
int c[N][N], tar[N][N];
//c : 费用
//tar ：存下每个点能到的点
/*为什么要特意存下每个点到的点？
答案其实并不困难，加快访问速度*/
int ans = INF, tmp, tot, cnt, n, m, p;
//ans : 最终的答案
//tmp : 最优解剪枝用
//tot : dfs储存中间答案的用具
//cnt ：现在已经访问过的点数
//n : 点数
//m : 边数
//p : sort用品

inline bool cmp(int a, int b) {
    return c[p][a] < c[p][b];
    //按照费用给每个点能到的点排序
}

inline void dfs(int num, int node) {
    for(int i = num; i <= cnt; i ++) {
        //由第几个被访问的点来扩展
        if(tot + tmp * lev[vis[i]] >= ans) return;
        //最优性剪枝，如果当前解加上理论最小的费用都比中途的答案高
        //那么这次搜索一定不是最优解
        for(int j = node; j <= d[vis[i]]; j ++)
        //下一步扩展谁
        if(!lev[tar[vis[i]][j]]) { //用lev同时充当标记，有lev代表已访问
            cnt ++; //多添加一个点
            vis[cnt] = tar[vis[i]][j]; //记录这个点
            tmp -= c[vis[cnt]][tar[vis[cnt]][1]]; //理论最小的更新
            tot += c[vis[i]][vis[cnt]] * lev[vis[i]]; //加上当前的影响
            lev[vis[cnt]] = lev[vis[i]] + 1; //因为从vis[i]拓展，故lev一定为其 + 1
            dfs(i, j + 1); //继续从i枚举, 注意到tar[i][1 ~ j]已全部访问，下一次从j + 1尝试访问
            tot -= c[vis[i]][vis[cnt]] * lev[vis[i]]; //回溯
            lev[vis[cnt]] = 0; //回溯
            tmp += c[vis[cnt]][tar[vis[cnt]][1]]; //回溯
            cnt --; //回溯
        }
        node = 1; //剪枝别剪错了，i枚举玩下次还要从1枚举
    }
    if(cnt == n) { //已经访问了n个点，更新答案
        if(tot < ans) ans = tot;
        return;
    }
}

int main() {
    int u, v, w;
    scanf("%d%d", &n, &m); //读入n, m
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
    c[i][j] = INF; //初始赋无限大，方便后面的操作
    for(int i = 1; i <= m; i ++) {
        scanf("%d%d%d", &u, &v, &w); //这个w先暂时存起来
        //因为发现m = 1000 远> n * n，所以要剪掉一些边
        if(c[u][v] < w) continue; //w不能更新c[u][v]
        if(c[u][v] == INF) //第一次更新c[u][v]，统计u,v的出度
        tar[u][++ d[u]] = v, tar[v][++ d[v]] = u;
        c[u][v] = c[v][u] = w;
    }
    for(int i = 1; i <= n; i ++) {
        p = i; //sort排序cmp
        sort(tar[i] + 1, tar[i] + 1 + d[i], cmp);
        tmp += c[i][tar[i][1]]; //因为每个点总要扩展一条边，
        //因此我们把最小的边找出来,作为最优性剪枝
        //不仅如此，因为边越小作为最终解的可能性越大
        //实际上在一定程度上优化了程序
    }
    for(int i = 1; i <= n; i ++) {
        tot = 0; cnt = 1; //赋初值
        vis[1] = i; //第一个就选i
        tmp -= c[i][tar[i][1]]; //i的最优性剪枝的影响要去掉
        //因为剪枝的时候是以还未访问和还未将被访问的点为基础的
        //不去掉剪枝就是错误的
        lev[i] = 1; //赋值
        dfs(1, 1); //只有一个点，也肯定是从1枚举
        lev[i] = 0; //回溯
        tmp += c[i][tar[i][1]];
    }
    printf("%d", ans);
    return 0;
}
int get_cost(int cur, int pre)
{
    if ((ne[pre] & cur) != cur) return -1;
    int remain = pre ^ cur;
    int cost = 0;
    for (int i = 0; i < n; i ++ )
    {
        if (remain >> i & 1)
        {
            int t = INF;
            for (int j = 0; j < n; j ++ )
                if (pre >> j & 1)
                    t = min(t, g[j][i]);
            cost += t;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i <= n; i ++ ) g[i][i] = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u --, v --;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    for (int st = 1; st < 1 << n; st ++ )   // 处理合法转移
        for (int i = 0; i < n; i ++ )
            if (st >> i & 1)
            {
                for (int j = 0; j < n; j ++ )
                    if (g[i][j] != INF)
                    {
                        ne[st] |= 1 << j;
                    }
            }
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < n; i ++ ) f[1 << i][0] = 0;    // 起点
    for (int i = 1, cost; i < 1 << n; i ++ )
        for (int j = (i-1)&i; j; j = (j-1)&i)
            if (~(cost = get_cost(i, j)))
            {
                for (int k = 1; k < n; k ++ )
                {
                    f[i][k] = min(f[i][k], f[j][k-1] + cost * k);
                }
            }
    int res = INF;
    for (int k = 0; k < n; k ++ )
        res = min(res, f[(1 << n) - 1][k]); // 目标状态找最优解
    printf("%d", res);
}
    for (int i = 2; i <= n; i ++ )
    {
        scanf("%lld", &sd[i]);
        sd[i] += sd[i-1];
    }
    for (int i = 1; i <= m; i ++ )
    {
        int h;
        scanf("%d%lld", &h, &t[i]);
        a[i] = t[i] - sd[h];
    }
    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i ++ ) s[i] = s[i-1] + a[i];

    memset(f, 0x3f, sizeof f);  // 去掉不合法状态
    //for (int i = 0; i <= p; i ++ ) f[i][0] = 0;    // 初态
    f[0][0] = 0;
    for (int j = 1; j <= p; j ++ )
    {
        int hh = 0, tt = 0;
        q[0] = 0;   // 隐含
        for (int i = 1; i <= m; i ++ )
        {
            while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j))
            <= a[i] * (q[hh + 1] - q[hh]))
                hh ++;
            int k = q[hh];
            f[j][i] = i * a[i] - s[i] + f[j-1][k] + s[k] - a[i] * k;
            while (hh < tt && (get_y(q[tt], j) - get_y(q[tt-1], j)) * (i - q[tt]) 
            >= (get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt-1]))
                tt --;
            q[ ++ tt] = i;
        }
    }
    printf("%lld", f[p][m]);
}
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &st[i], &sc[i]);
        st[i] += st[i-1], sc[i] += sc[i-1];
    }

    hh = 0, tt = 0, q[tt] = 0;  // 用队头的两个元素维护大于当前斜率 ki 的最小斜率 kqhh,
    for (int i = 1; i <= n; i ++ )
    {
        while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (sc[q[hh + 1]] - sc[q[hh]]) * (st[i] + S)) 
            hh ++;  // 如果 <= 当前点的斜率，可以删掉
        int j = q[hh];
        f[i] = f[j] + S * (sc[n] - sc[j]) + st[i] * (sc[i] - sc[j]);
        while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]]) >= (f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]))
            tt --;  // 把单调队列内不在凸包上的点删掉
        q[ ++ tt] = i;
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = v1; j >= x[i]; j -- )
            for (int k = v2 - 1; k >= y[i]; k -- )
            {
                f[j][k] = max(f[j][k], f[j - x[i]][k - y[i]] + 1);
            }
    }
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= K; i ++ )
    {
        for (int j = m - 1; j >= y[i]; j -- )
            for (int k = K; k >= 1; k -- )
                if (f[j - y[i]][k - 1] + x[i] <= n)
                {
                    f[j][k] = min(f[j][k], f[j - y[i]][k - 1] + x[i]);
                }
    }

    for (int k = K; k >= 0; k -- )
    {
        int p = INF;
        for (int j = 0; j < m; j ++ )
        {
            if (f[j][k] != INF && j < p)
            {
                p = j;
            }
        }
        if (p != INF) {printf("%d %d", k, m - p); return 0;}
    }
void dfs(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        for (int k = m - v[u]; k >= 0; k -- )
            for (int t = 0; t <= k; t ++ )
            {
                f[u][k] = max(f[u][k], f[u][k - t] + f[j][t]);
            }
    }
    for (int k = m; k >= v[u]; k -- ) f[u][k] = f[u][k - v[u]] + w[u];
    for (int k = 0; k < v[u]; k ++ ) f[u][k] = 0;
}
    scanf("%d%s", &n, str + 1);
    int m = strlen(str + 1);
    for (int i = 2, j = 0; i <= m; pmt[i ++ ] = j)
    {
        while (j && str[i] != str[j + 1]) j = pmt[j];
        if (str[i] == str[j + 1]) j ++;
    }

    f[0][0] = 1;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            for (char k = 'a'; k <= 'z'; k ++ )
            {
                int u = j;
                while (u && k != str[u + 1]) u = pmt[u];
                if (k == str[u + 1]) u ++;
                if (u < m) f[i+1][u] = ((LL)f[i+1][u] + f[i][j]) % mod;
            }
    int res = 0;
    for (int i = 0; i < m; i ++ ) res = ((LL)res + f[n][i]) % mod;
    printf("%d", res);
int n, m;
int a[N];

struct Smtree
{
    int l, r;
    int sum;    // 区间和
    int add;    // 懒标记, 表示其子树上的所有节点都要加上add
}seg[N * 4];

void pushup(int p)  // 由下往上传递信息
{
    seg[p].sum = seg[p * 2].sum + seg[p * 2 + 1].sum;
}

void pushdown(int p)// 由上往下传递信息
{
    Smtree &fa = seg[p];
    Smtree &left = seg[p * 2], &right = seg[p * 2 + 1];

    if (fa.add)
    {
        left.add += fa.add;
        left.sum += (left.r - left.l + 1) * fa.add;
        right.add += fa.add;
        right.sum += (right.r - right.l + 1) * fa.add;
        fa.add = 0;
    }
}

void build(int p, int l, int r)
{
    seg[p].l = l, seg[p].r = r;
    if (l == r) { seg[p] = {l, r, a[l], 0}; return;}
    int mid = l + r >> 1;
    build(p * 2, l, mid);           // 左子树
    build(p * 2 + 1, mid + 1, r);   // 右子树

    pushup(p);                      // 由下往上传递信息
}

void change(int p, int l, int r, int d)
{
    if (seg[p].l >= l && r >= seg[p].r) 
    {
        seg[p].sum += (seg[p].r - seg[p].l + 1) * d;
        seg[p].add += d;
        return;
    }

    pushdown(p);// 由上往下传递信息

    int mid = seg[p].l + seg[p].r >> 1;     // 折半
    if (l <= mid) change(p * 2, l, r, d);   // 左子树
    if (r > mid) change(p * 2 + 1, l, r, d);// 右子树

    pushup(p);  // 由下往上传递信息
}

int query(int p, int l, int r)
{
    if (seg[p].l >= l && r >= seg[p].r) return seg[p].sum;

    pushdown(p);

    int mid = seg[p].l + seg[p].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(p * 2, l, r);     // 左子树的部分
    if (r > mid) sum += query(p * 2 + 1, l, r); // 加上右子树的部分
    return sum; // 直接返回

}
int n, m, a[N];
vector<int> nums;

struct Node
{
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N], idx;

int find(int x)
{
    int l = 0, r = nums.size(), mid;
    while (l < r) {
        mid = l + r >> 1; 
        if (nums[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int build(int l, int r)
{
    int p = ++ idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];  // 左右指针指向上一次的点
    if (l == r)
    {
        tr[q].cnt ++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x); // 修改指针
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k)
{
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);    // 求的是第k大
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    root[0] = build(0, nums.size()-1);

    for (int i = 1; i <= n; i ++ )
        root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));

    while (m -- )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l-1], 0, nums.size() - 1, k)]);
    }
}
int n;
struct Node
{
    int s[2], p, v;
    int size, cnt;
    void init(int _v, int _p)
    {
        p = _p, v = _v;
        size = cnt = 1;
    }
}tr[N];
int root, idx;

void pushup(int x)
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + tr[x].cnt;
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k^1], tr[tr[x].s[k^1]].p = y;
    tr[x].s[k^1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
        {
            if ((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) root = x;
}

void insert(int v)
{
    int u = root, p = 0;
    while (u) 
    {
        p = u;
        if (v == tr[u].v)
        {
            tr[u].cnt ++;
            splay(u, 0);
            return;
        }
        u = tr[u].s[v > tr[u].v];
    }
    u = ++ idx;
    if (p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0);
}

int get(int v)  // >= 的最小数
{
    int u = root, res;
    while (u)
    {
        if (v <= tr[u].v) res = u, u = tr[u].s[0];
        else u = tr[u].s[1];
    }
    splay(res, 0);
    return tr[tr[res].s[0]].size;
}

int get_k(int k)
{
    int u = root;
    while (u)
    {
        int l = tr[u].s[0], r = tr[u].s[1];
        if (tr[l].size >= k) u = l;
        else if (tr[l].size + tr[u].cnt >= k) return u;
        else k -= tr[l].size + tr[u].cnt, u = r;
    }
    return -1;
}

int next(int x, int f)
{
    int u = root;
    if ((tr[u].v > x && f) || (tr[u].v < x && !f))
        return tr[u].v;
    u = tr[u].s[f];
    while (tr[u].s[f^1])
        u = tr[u].s[f^1];
    return tr[u].v;
}
int tr[2][N];
ll f[2][39],ans,inv;
vector<int> pos[N];
int n,a[N],cnt=1;

inline void insert(int x,int v,int p,int k)
{
    if(k<0) return;
    int c=(v>>k)&1;
    if(!tr[c][x]) tr[c][x]=++cnt;
    pos[tr[c][x]].push_back(p);
    insert(tr[c][x],v,p,k-1);
}

void dfs(int u,int p)
{
    int ls=tr[0][u],rs=tr[1][u];
    if(ls) dfs(ls,p-1);
    if(rs) dfs(rs,p-1);
    if(!ls&&!rs) return;
    int num=0;
    ll res=0;
    for(auto i:pos[ls])
    {
        while(num<pos[rs].size()&&pos[rs][num]<i) ++num;
        res+=num;
    }
    f[0][p]+=res;
    f[1][p]+=1ll*pos[ls].size()*pos[rs].size()-res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        insert(1,a[i],i,29);
    }
    dfs(1,29);
    for(int i=29;i>=0;i--)
    {
        inv+=min(f[0][i],f[1][i]);
        if(f[1][i]<f[0][i])
            ans|=(1<<i);
    }
    printf("%lld %lld",inv,ans);
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

const int N = 300010, M = N * 2, L = 19; // 2^L > N

typedef pair<int, int> PII;

int n, m;   // 结点数, 玩家数;
int h[N], e[M], ne[M], idx; // 邻接表存边
int depth[N], fa[N][L];     // 往上跳 2^0 ~ 2^19 步后的父亲节点

int ans[N];     // 答案数组
int Time[N];    // 出现观察员的时间
int da[M], db[M];
bool st[N];     // Dfs 时避免重复搜索
queue<int> q;   // Bfs 队列

vector<PII> botel[N];   // 在同一条链上
vector<PII> dotel[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)  // Lca 预处理
{
    memset(depth, 0x3f, sizeof depth);  // 预处理
    depth[0] = 0, depth[root] = 1;      // 根结点的深度为1

    q.push(root);       // 从根节点开始遍历
    while (q.size())    // 队列不空
    {
        int t = q.front();  // 取出队头
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];   // 取与 t 相连接的节点
            if (depth[j] > depth[t] + 1)    // 当前点过深, 也就是没有更新过
            {
                depth[j] = depth[t] + 1;    // 更新
                q.push(j);                  // 加入队头
                fa[j][0] = t;               // 父节点为 t

                for (int k = 1; k <= L - 1; k ++ ) // 预处理 fa[j] 往上走 2^{1 ~ 18} 步的父节点
                {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                    // 因为BFS的 最短路性质,  所以一定是正确的
                }
            }
        }
    }
}

int lca(int a, int b)   // 求最近公共祖先, 复杂度 O(log n)
{
    if (depth[a] < depth[b]) swap(a, b);    // 选深的

    for (int k = L - 1; k >= 0; k -- )      // 往上跳, 二进制拆分思想
        if (depth[fa[a][k]] >= depth[b])
        {
            a = fa[a][k];
        }
    if (a == b) return a;
    for (int k = L - 1; k >= 0; k -- )      // 同时往上跳
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

void update(int s, int t)   // 玩家轨迹
{
    int p = lca(s, t), f = fa[p][0];    // 找出 父节点 和 父节点的祖先
    // 树上差分
    botel[s].push_back({depth[s], 1});  // 要走的
    botel[f].push_back({depth[s], -1}); // 不走的

    int Lenth = depth[s] - 2 * depth[p] + n;    // 有分叉的路径
    dotel[t].push_back({Lenth, 1});     // 要走的
    dotel[p].push_back({Lenth, -1});    // 不走的
}

void dfs(int u) // 统计答案
{
    int Va = Time[u] + depth[u], Vb = Time[u] - depth[u] + n;   // 转换操作
    // Va 是一条链情况, Vb 是分叉情况
    int res1 = da[Va], res2 = db[Vb];

    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }

    for (int i = 0; i < botel[u].size() || i < dotel[u].size(); i ++ )
    {
        if (i < botel[u].size()) da[botel[u][i].first] += botel[u][i].second;   
        if (i < dotel[u].size()) db[dotel[u][i].first] += dotel[u][i].second;
    }
    ans[u] = (da[Va] - res1) + (db[Vb] - res2);
}

int main()
{
    memset(h, -1, sizeof h);    // 预处理
    scanf("%d %d", &n, &m);

    for (int i = 1; i < n; i ++ )
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);   // 加双向边
    }
    for (int i = 1; i <= n; i ++ ) scanf("%d", &Time[i]);

    int root = 1;   // 根在一号节点
    bfs(root);  

    for (int i = 1; i <= m; i ++ )  // 读入玩家
    {
        int s, t;
        scanf("%d %d", &s, &t);
        update(s, t);               // 在线给答案
    }
    dfs(1);

    for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);

    return 0;
}
int prime[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int rec[16], a[16], n;
double recv = 1e13, val[16];

struct num
{
    ll data[10005];
    num operator * (const int b) const
    {
        num c;
        memcpy(c.data, data, sizeof(data));
        for (int i = 1; i <= c.data[0]; i++)
            c.data[i] *= b;
        for (int i = 1; i <= c.data[0]; i++)
        {
            if (c.data[i] >= 10000)
            {
                c.data[i + 1] += c.data[i] / 10000;
                c.data[i] %= 10000;
            }            
        }
        ll &h = c.data[0];
        while (c.data[h + 1] > 0)
        {
            h++;
            c.data[h + 1] += c.data[h] / 10000;
            c.data[h] %= 10000;
        }
        return c;
    }
    void print()
    {
        printf("%lld", data[data[0]]);
        for (int i = data[0] - 1; i >= 1; i--)
        {
            if (data[i] <= 9)
                printf("000");
            else if (data[i] <= 99)
                printf("00");
            else if (data[i] <= 999)
                printf("0");
            printf("%lld", data[i]);           
        }

    }
} ans;//高精乘

void dfs(int poi, int now, int last, double temp)
{
    if (poi == 16 || temp > recv || n % now)
        return;
    if (now == n)
    {
        if (temp < recv)
        {
            recv = temp;
            memcpy(a, rec, sizeof(rec));
        }
        return;
    }
    double t = val[poi];
    int k = n / now;
    for (int i = min(k - 1, last); i >= 0; --i)
    {
        rec[poi] = i;
        dfs(poi + 1, now * (i + 1), i, temp + i * t);
    }
    rec[poi] = 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 16; i++)
        val[i] = log(prime[i]);
    dfs(0, 1, n - 1, 0);
    ans.data[0] = ans.data[1] = 1;
    for (int i = 0; i < 16; i++)
        while (a[i]--)
            ans = ans * prime[i];
    ans.print();
}
for (int i=1;i<=n;i++){
    scanf ("%d",&c[i]);
    s[c[i]][i%2]++;//求出这个分组中有多少个数
    sum[c[i]][i%2]=(sum[c[i]][i%2]+x[i])%10007;//事先求出累加和，注意，要mod10007
}
for (int i=1;i<=n;i++){
    ans=(ans+i*((s[c[i]][i%2]-2)*x[i]%10007+sum[c[i]][i%2]))%10007;//依次然后代入，注意，也要mod10007
}
printf ("%d\n",ans);//最后输出
priority_queue<LL, vector<LL>, greater<LL> > heap;

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++ )
    {
        LL d, p;
        scanf("%lld%lld", &d, &p);
        q[i] = {d, p};
    }
    sort(q + 1, q + n + 1);
    for (int i = 1; i <= n; i ++ )
    {
        if (q[i].first <= heap.size())  // 时间消耗 = 堆的大小
        {
            if (q[i].second > heap.top())
            {
                ans += q[i].second - heap.top();
                heap.pop();
                heap.push(q[i].second);
            }
        }
        else 
        {
            ans += q[i].second;
            heap.push(q[i].second);
        }
    }
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXR_C 1000005
#define IL inline
using namespace std ;
vector <int> v[MAXN] , V[MAXN];
vector <int> xi[MAXR_C] , yi[MAXR_C] ;
struct MMP {
    int  ax , ay , az ;
}a[MAXN];
int n , R , C ;
int sta[MAXN] , top , dfn[MAXN] , low[MAXN] , deg[MAXN];
int col_sum[MAXN] , cnt , sum , pio[MAXN] , f[MAXN];
bool In_it[MAXN] ;
queue <int> q ;
IL void tarjan(int x) {
    In_it[x] = 1; 
    dfn[x] = low[x] = ++cnt ;
    sta[++top] = x ;
    for(int i=0; i<v[x].size(); i++) {
        int u = v[x][i] ; 
        if(!dfn[u]) {
            tarjan(u) ; 
            low[x] = min(low[x] , low[u]) ;
        } else if(In_it[u]) 
          low[x] = min(low[x] , dfn[u]) ; 
    }
    if(dfn[x] == low[x])  {
        sum ++ ;
        int per = sta[top] ;
        while(per != x) {
            col_sum[sum]++ ;
            In_it[per] = 0;
            pio[per] = sum ;
            per = sta[--top] ;
        }
        pio[x] = sum ;
        col_sum[sum] ++ ;
        In_it[x] = 0;
        top -- ;
    }
}
int main() 
{
    int x , y , z , Ans = 0;
    cin >> n >> R >> C ;
    for(int i=1; i<=n; i++)  {
        cin >> a[i].ax >> a[i].ay >> a[i].az ;
        xi[a[i].ax].push_back(i) ;
        yi[a[i].ay].push_back(i) ;
    }
    for(int i=1; i<=n; i++) {
        x = a[i].ax ; y =a[i].ay ; z = a[i].az ;
        if( z == 1 ) {
            for(int j=0; j<xi[x].size(); j++) {
                int u = xi[x][j] ;
                if(u == i) continue ;
                v[i].push_back(u) ;
            }
        } else if(z == 2) {
            for(int j=0; j<yi[y].size(); j++) {
                int u = yi[y][j] ;
                if(u == i) continue ;
                v[i].push_back(u) ;
            }
        } else if(z == 3) {
            if(x > 1) {
                for(int j=0; j<xi[x-1].size(); j++) {
                   int u = xi[x-1][j] ;
                   if(y-1<=a[u].ay && a[u].ay<=y+1) 
                     v[i].push_back(u) ;
                }
            } 
            for(int j=0; j<xi[x].size(); j++) {
                int u = xi[x][j] ;
                if(u == i) continue ;
                if(y-1<=a[u].ay && a[u].ay<=y+1) 
                     v[i].push_back(u) ;
            } 
            if(x < R) {
                for(int j=0; j<xi[x+1].size(); j++) {
                    int u = xi[x+1][j] ;
                    if(y-1<=a[u].ay && a[u].ay<=y+1) 
                      v[i].push_back(u) ;
                }
            }
        }
   }
    for(int i=1; i<=n; i++)
      if(!dfn[i]) tarjan(i) ;
    for(int i=1; i<=n; i++)
      for(int j=0; j<v[i].size(); j++) {
        int u = v[i][j] ;
        if(pio[u] == pio[i]) continue ;
        deg[pio[u]] ++ ;
        V[pio[i]].push_back(pio[u]) ;
      }
    for(int i=1; i<=sum; i++)
     if(!deg[i]) f[i]=col_sum[i],q.push(i) ;
    while(!q.empty()) {
        int u = q.front() ; q.pop() ;
        for(int i=0; i<V[u].size(); i++) {
            int so = V[u][i] ;
            f[so] = max(f[so] , f[u]+col_sum[so]) ;
            Ans = max(Ans , f[so]) ;
            deg[so] -- ;
            if(!deg[so])  
              q.push(so) ;
        }
    }
    cout << Ans << endl;
    return  0 ;
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;

int prime[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int rec[16], a[16], n;
double recv = 1e13, val[16];

struct num
{
    ll data[10005];
    num operator * (const int b) const
    {
        num c;
        memcpy(c.data, data, sizeof(data));
        for (int i = 1; i <= c.data[0]; i++)
            c.data[i] *= b;
        for (int i = 1; i <= c.data[0]; i++)
        {
            if (c.data[i] >= 10000)
            {
                c.data[i + 1] += c.data[i] / 10000;
                c.data[i] %= 10000;
            }
        }
        ll &h = c.data[0];
        while (c.data[h + 1] > 0)
        {
            h++;
            c.data[h + 1] += c.data[h] / 10000;
            c.data[h] %= 10000;
        }
        return c;
    }
    void print()
    {
        printf("%lld", data[data[0]]);
        for (int i = data[0] - 1; i >= 1; i--)
        {
            if (data[i] <= 9)
                printf("000");
            else if (data[i] <= 99)
                printf("00");
            else if (data[i] <= 999)
                printf("0");
            printf("%lld", data[i]);
        }

    }
} ans;//高精乘

void dfs(int poi, int now, int last, double temp)
{
    if (poi == 16 || temp > recv || n % now)
        return;
    if (now == n)
    {
        if (temp < recv)
        {
            recv = temp;
            memcpy(a, rec, sizeof(rec));
        }
        return;
    }
    double t = val[poi];
    int k = n / now;
    for (int i = min(k - 1, last); i >= 0; --i)
    {
        rec[poi] = i;
        dfs(poi + 1, now * (i + 1), i, temp + i * t);
    }
    rec[poi] = 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 16; i++)
        val[i] = log(prime[i]);
    dfs(0, 1, n - 1, 0);
    ans.data[0] = ans.data[1] = 1;
    for (int i = 0; i < 16; i++)
        while (a[i]--)
            ans = ans * prime[i];
    ans.print();
}
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100005;

int f[N];
int g[400][N];
int main() {
    int n, p;
    cin >> n >> p;
    int m = sqrt(n) + 1;
    f[0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = i; j <= n; j++) {
            f[j] += f[j - i];
            f[j] %= p;
        }
    }
    g[0][0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = i; j <= n; j++) {
            g[i][j] = g[i][j - i];
            if (j >= m) g[i][j] += g[i - 1][j - m];
            g[i][j] %= p;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        LL sum = 0;
        for (int j = 0; j < m; j++) sum += g[j][n - i];
        sum %= p;
        ans = (ans + f[i] * sum) % p;
    }
    cout << ans << endl;
    return 0;
}