#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[], int l, int r){
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j){
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[], int l, int r, int k){
    if (l >= r) return q[l];
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j){
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    if (j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    cout << quick_sort(q, 0, n - 1, k) << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    return 0;
}

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else{
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    cout << merge_sort(a, 0, n - 1) << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    while (m -- ){
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) cout << "-1 -1" << endl;
        else{
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    double x;
    cin >> x;
    double l = -100, r = 100;
    while (r - l > 1e-8){
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf
", l);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}
int main(){
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B){
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    vector<int> C;
    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- ){
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a;
    vector<int> A;
    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    int r;
    auto C = div(A, B, r);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl << r << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化
    while (m -- ){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d
", s[r] - s[l - 1]); // 区间和的计算
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    while (q -- ){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d
", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
    while (m -- ){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
    while (q -- ){
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], s[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ ){
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main(){
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0, j = m - 1; i < n; i ++ ){
        while (j >= 0 && a[i] + b[j] > x) j -- ;
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int x, s = 0;
        scanf("%d", &x);
        for (int i = x; i; i -= i & -i) s ++ ;
        printf("%d ", s);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
int find(int x){
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ ){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 处理插入
    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    // 处理询问
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first){
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}
int main(){
    int n;
    scanf("%d", &n);
    vector<PII> segs;
    for (int i = 0; i < n; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

#include<iostream>
#include<stack>
using namespace std;
stack<int> stk;
const int N = 100005;
int arr[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++) {
        while (!stk.empty()&&arr[i] <= stk.top())
            stk.pop();
        if (stk.empty())
            cout << -1 << " ";
        else cout << stk.top() << " ";
        stk.push(arr[i]);
    }
    return 0;
}

#include<iostream>
#include<deque>
using namespace std;
deque<int> dq;
const int N = 1000005;
int arr[N];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++) {
        if (!dq.empty() && i - k + 1 > dq.front())
            dq.pop_front();
        while (!dq.empty() && arr[dq.back()] >= arr[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1)
            cout << arr[dq.front()]<<" ";
    }
    dq.clear();
    cout << endl;
    for (int i = 0; i < n; i++) {
        if (!dq.empty() && i - k + 1 > dq.front())
            dq.pop_front();
        while (!dq.empty() && arr[dq.back()] <= arr[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) 
            cout << arr[dq.front()] << " ";
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i ++ ){
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; i ++ ){
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}
/*下标从0开始
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
char s[N], p[N];
int ne[N];
int main(){
    cin >> m >> p >> n >> s;
    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ ){
        while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }
    for (int i = 0, j = -1; i < n; i ++ ){
        while (j != -1 && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m - 1){
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d
", query(str));
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;
void insert(int x){
    int p = 0;
    for (int i = 30; i >= 0; i -- ){
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}
int search(int x){
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- ){
        int s = x >> i & 1;
        if (son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
    printf("%d
", res);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    while (m -- ){
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[find(a)] = find(b);
        else{
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N], cnt[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        cnt[i] = 1;
    }
    while (m -- ){
        string op;
        int a, b;
        cin >> op;
        if (op == "C"){
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b){
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1"){
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u){
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t){
        swap(h[u], h[t]);
        down(t);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;
    for (int i = n / 2; i; i -- ) down(i);
    while (m -- ){
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }
    puts("");
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少
//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v){   
    swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            
}
void down(int u){
    int t=u;
    if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
void up(int u){
    if(u/2>0&&h[u]<h[u/2]) {
        heap_swap(u,u/2);
        up(u>>1);
    }
}
int main(){
    int n;
    cin>>n;
    int m=0;      //m用来记录插入的数的个数
                //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--){
        string op;
        int k,x;
        cin>>op;
        if(op=="I"){
            cin>>x;
            m++;
            h[++cur_size]=x;
            ph[m]=cur_size;
            hp[cur_size]=m;
            //down(size);
            up(cur_size);
        }
        else if(op=="PM")    cout<<h[1]<<endl;
        else if(op=="DM"){
            heap_swap(1,cur_size);
            cur_size--;
            down(1);
        }
        else if(op=="D"){
            cin>>k;
            int u=ph[k];//这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,cur_size);//因为在此处heap_swap操作后ph[k]的值已经发生 
            cur_size--;//如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
           down(u);
        }
        else if(op=="C"){
            cin>>k>>x;
            h[ph[k]]=x;//此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            down(ph[k]);//所以可直接传入ph[k]作为参数
            up(ph[k]);
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while (m -- ){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
void dfs(int u, int state){
    if (u == n){
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!(state >> i & 1)){
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));
        }
}
int main(){
    scanf("%d", &n);
    dfs(0, 0);
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
bool chosen[30];
int n, m;
vector<int> nums;
void dfs(int pos) {
    if (nums.size() > m || nums.size() + n - pos + 1 < m)
        return;
    if (nums.size() == m) {
        for (int i = 0; i < nums.size(); i++)
            cout << nums[i]<<" ";
        cout << endl;
        return;
    }
    nums.push_back(pos);
    dfs(pos + 1);
    nums.pop_back();
    dfs(pos + 1);
}
int main() {
    cin >> n >> m;
    dfs(1);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    dfs(0);
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
int bfs(){
    queue<PII> q;
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (q.size()){
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++ ){
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 100005;
vector<int> g[N];
int n;
int st[N];
int ans = N;
int dfs(int u) {
    st[u] = true;
    int sum = 1, res = 0;
    for (auto node : g[u]) {
        if (!st[node]) {
            int s = dfs(node);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}
int main() {
    cin >> n;
    for(int i=0;i<n-1;i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    cout << ans;
    return 0;
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 100010;
int n, m;
vector<int> graph[N];
vector<int> path;
int ind[N];//入度
bool toposort() {
    int indnode = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            indnode = i;
            q.push(i);
        }
    }
    if (indnode == 0)
        return false;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        path.push_back(cur);
        for (auto node : graph[cur]) {
            ind[node]--;
            if (ind[node] == 0)
                q.push(node);
        }
    }
    for (int i = 1; i <= n; i++)
        if (ind[i] > 0)
            return false;
    return true;
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        ind[y]++;
    }
    if (toposort()) {
        for (auto node : path)
            cout << node << " ";
    }
    else 
        cout << -1;
    return 0;
}

#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, vector<int> > PIV;
priority_queue<PIV, vector<PIV>,greater<PIV> > q;
map<vector<int>, string> path;
map<vector<int>, int> dist;
vector<int> endst = { 1,2,3,4,5,6,7,8,0 };
int pred(vector<int> state,int steps) {
    int res = 0;
    for (int i = 0; i < 9; i++)//这里1~8对应的下标为0~7
        if (state[i] != 0) {
            int t = state[i] - 1;//对应下标
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);//曼哈顿距离
        }
    return res+steps;//返回总曼哈顿距离
}
int mfind(vector<int> state) {
    for (int i = 0; i < 9; i++)
        if (state[i] == 0)
            return i;
    return -1;
}
void bfs() {
    while (!q.empty()) {
        PIV cur = q.top();
        q.pop();
        if (cur.second ==endst) {
            cout << path[cur.second];
            return;
        }
        int pos = mfind(cur.second);
        if (pos / 3 == 0) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos + 3]);
            if (path.count(newc) == 0||dist[newc]>dist[cur.second]+1) {
                path[newc] = path[cur.second] + "d";
                dist[newc] = dist[cur.second] + 1;
                q.push({pred(newc,dist[newc]),newc });
            }
        }
        if (pos / 3 == 1) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos + 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "d";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
            newc = cur.second;
            swap(newc[pos], newc[pos - 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "u";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos / 3 == 2) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos - 3]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "u";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 0) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos + 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "r";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 1) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos + 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "r";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
            newc = cur.second;
            swap(newc[pos], newc[pos - 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "l";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
        if (pos % 3 == 2) {
            vector<int> newc = cur.second;
            swap(newc[pos], newc[pos - 1]);
            if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) {
                path[newc] = path[cur.second] + "l";
                dist[newc] = dist[cur.second] + 1;
                q.push({ pred(newc,dist[newc]),newc });
            }
        }
    }
}
int nixu(vector<int> state) {
    int res = 0;
    for (int i = 0; i < 9; i++) {
        for (int j = i; j < 9; j++)
            if (state[j] < state[i] && state[j] != 0)
                res++;
    }
    return res;
}
int main() {
    vector<char> ch(9);
    for (int i = 0; i < 9; i++)
        cin >> ch[i];
    vector<int> init(9);
    for (int i = 0; i < 9; i++) {
        if (ch[i] == 'x')
            init[i] = 0;
        else init[i] = ch[i] - '0';
    }
    if (nixu(init) % 2 == 0) {
        q.push({pred(init,0),init });
        dist[init] = 0;
        path[init] = "";
        bfs();
        return 0;
    }
    else {
        cout << "unsolvable";
        return 0;
    }
}

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];
void init(){
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool is_set){
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';
    int v = 1 << t;
    if (!is_set) v = -v;
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int lowbit(int x){
    return x & -x;
}
int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt){
    if (!cnt) return true;
    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.'){
                int state = get(i, j);
                if (ones[state] < minv){
                    minv = ones[state];
                    x = i, y = j;
                }
            }
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i)){
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }
    return false;
}
int main(){
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;
    while (cin >> str, str[0] != 'e'){
        init();
        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;
        dfs(cnt);
        puts(str);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int t,c,ts,te;
int ans=0;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
int st[2505];
int dist[2505];
vector<PII> g[2505];
void dijkstra(){
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[ts]=0;
    q.push({0,ts});
    while(!q.empty()){
        auto [d,cur]=q.top();
        q.pop();
        if (st[cur])
            continue;
        st[cur]=1;
        for(auto node:g[cur]){
            auto [d,next]=node;
            if (d+dist[cur]<dist[next]){
                dist[next]=d+dist[cur];
                q.push({dist[next],next});
            }
        }
    }
}
int main(){
    cin>>t>>c>>ts>>te;
    for(int i=1;i<=c;i++){
        int rs,re,ci;
        cin>>rs>>re>>ci;
        g[rs].push_back({ci,re});
        g[re].push_back({ci,rs});
    }
    dijkstra();
    cout<<dist[te];
}

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int n, m;
const int N = 100005;
int dist[N];
typedef  pair<int, int> PII;//first表示指向点，second表示距离
vector<PII> graph[N];
void spfa() {
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int curnode = q.front();
        q.pop();
        for (auto node : graph[curnode]) {
            if (dist[node.first] > dist[curnode] + node.second) {
                dist[node.first] = dist[curnode] + node.second;
                q.push(node.first);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({ y,z });
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    spfa();
    if (dist[n] > 0x3f3f3f3f / 2)
        cout << "impossible";
    else
        cout << dist[n];
    return 0;
}