CF #5 sol

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
const int mod = 1e9 + 7;

signed main()
{
    _FastIO;
    /*
    // A
    int n , x;
    cin >> n;
    vector<pair<int , int> > v; // {value , index}
    for(int i = 1; i <= n; i++){
        cin >> x;
        v.push_back({x , i});
    }
    sort(v.begin() , v.end());
    */
    /*
    4
    8 2 5 1

    {1 , 4} 0
    {2 , 2} 1
    {5 , 3} 2
    {8 , 1} 3

    */
    // 0    n-1
    // second best n-2
    //cout << v[n - 2].second << '\n';

    // 0 <= i < j < n
    /*
    // B
    int n;
    cin >> n;
    int a[n + 5];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            sum += a[i] * a[j];
            sum %= mod;
        }
    }

    cout << sum % mod << '\n';
    */

    // 1 2 3 4 5
    // (a + b) % mod = (a % mod + b % mod) % mod
    // (a * b) % mod = ((a % mod) * (b % mod)) % mod
    // (a - b) % mod = ((a % mod) - (b % mod)) % mod

    // (9 - 7) % 3 = 0 - 1 = -1 + mod = 2
    /*
    // G
    int n;
    cin >> n;
    int a[n + 5];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    int s = a[0] , ans = 0;
    for(int i = 1; i < n; i++){
        ans += s * a[i];
        ans %= mod;
        s += a[i];
        s %= mod;
    }
    cout << ans << '\n';*/
    /*
    // C
    string s;
    cin >> s;
    string ans = "NO";
    for(int i = 0; i < 5; i++){
        string a;
        cin >> a;
        if(a[0] == s[0] || a[1] == s[1])
            ans = "YES";
    }
    cout << ans << '\n';
    */

    // QAQAQYSYIOIWIN

    // 1 2 3 4 5   substring   subsequence
    // 1 2              +           +
    // 1 3              -           +
    // 2 4 5            -           +
    //  1               +           +
    //  1 2 3 4 5       +           +
    //  6               -           -
    // 4 2              -           -


    // i < j < k
    // Q   A   Q
    /*
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    // QAQ
    // QQQAQQ
    int q = 0 , qa = 0 , qaq = 0;
    for(char i : s){
        if(i == 'Q'){
            q++;
            qaq += qa;
        }

        if(i == 'A')
            qa += q;
    }
    cout << qaq << '\n';
    */
    /*
    // E
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        for(char i = 'a'; i <= 'h'; i++){
            if(i == s[0])
                continue;
            cout << i << s[1] << '\n';
        }
        for(int i = 1; i <= 8; i++){
            if(i == s[1] - '0')
                continue;
            cout << s[0] << i << '\n';
        }
    }
    */
    /*
    // F
    int t;
    cin >> t;
    char a[10][10];
    while(t--){
        for(int i = 1; i <= 8; i++){
            for(int j = 1; j <= 8; j++){
                cin>> a[i][j];
            }
        }

        for(int i = 2; i <= 7; i++){
            for(int j = 2; j <= 7; j++){
                if(a[i][j] == '#' && a[i - 1][j - 1] == '#' && a[i - 1][j + 1] == '#')
                    cout << i << " " << j << '\n';
            }
        }
    }
    */
    /*
    // H
    int t , n;
    cin >> t;
    while(t--){
        cin >> n;
        cout << n / 10 + n % 10 << '\n';
    }
    */
    /*
    a b
    c d

    a-c  b-d
    b-d  a-c
    a-d  b-c
    b-c  a-d
    */
    /*
    // I
    int t , a , b , c , d;
    cin >> t;
    while(t--){
        cin >> a >> b >> c >> d;
        int ans = 0;
        if(a >= c && b >= d && (a > c || b > d))
            ans += 2;

        if(b >= c && a >= d && (b > c || a > d))
            ans += 2;

        cout << ans << '\n';
    }
    */
    /*
    // J
    int t , n , s , m;
    cin >> t;
    while(t--){
        cin >> n >> s >> m;
        int pre = 0;
        string ans = "NO";
        while(n--){
            int l , r;
            cin >> l >> r;
            if(l - pre >= s)
                ans = "YES";
            pre = r;
        }
        if(m - pre >= s)
            ans = "YES";
        cout << ans << '\n';
    }
    */
    /*
    // K
    int t;
    cin >> t;
    while(t--){
        string a , b;
        cin >> a >> b;
        int n = a.size() , m = b.size();
        int j = 0;
        for(int i = 0; i < n; i++){
            if(j == m){
                if(a[i] == '?')
                    a[i] = 'a';
                continue;
            }
            if(a[i] == b[j]){
                j++;
                continue;
            }
            if(a[i] == '?'){
                a[i] = b[j];
                j++;
            }
        }
        if(j == m){
            cout << "YES" << '\n';
            cout << a << '\n';
        }else
            cout << "NO" << '\n';
    }
    */
}