DevTang | 唐巧修改

/*
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

long long n, m, a, b, d, ans;

bool test(long long k) {
    long long c1 = a*k;
    long long c2 = b*k;
    if (c1 > n) {
        long long r = (c1 - n + d - 1) / d;
        c1 -= r*d;
        c2 += r*d;
    }
    if (c1 <= n && c2 <=m) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(0);       
    cin >> n >> m >> a >> b;
    if (n < m) swap(n, m);
    if (a < b) swap(a, b);
    d = a - b;
    long long l = 0;
    long long r = n;
    while (l <= r) {
        long long m = (l+r)/2;
        if (test(m)) {
            ans = max(ans, m);
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
    return 0;
}

// 循环结构, 例如 for ...
    // 判断条件
// 输出结果

// 循环
for (int i = l; i <= r; ++i) {
    // 判断条件
    if (isLucky(i)) {
        // 累加
        ans += i;
    }
}
// 输出结果
cout << ans << endl;

// 循环
for (int i = 1; i <= n; ++i) {
    cin >> a;
    b = a%10;
    a = a/10;
    // 判断条件
    if (b <= 4) a = a*10;
    else a = a*10 + 10;
    // 输出结果
    cout << a << endl;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
int tu[55][55];
int main() {
    cin >> n >> m;
    // 嵌套的 for 循环
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << i*j << " ";
        }
        cout << endl;
    }
    return 0;
}

bool isPrime(int a) {
    for (int i = 2; i*i <=a; i++) {
        if (a%i == 0) {
            return false;
        }
    }
    return true;
}

bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int count(int a, int k) {
    int ret = 0;
    while (a) {
        if (a%10 == k) ret++;
        a/=10;
    }
    return ret;
}

bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        cin >> s;
        bool ans = false;
        if (s.length() >= 4) {
            for (int i = 2; i < s.length() - 1; i++) {
                string s1 = s.substr(0, i);
                string s2 = s.substr(i);
                if (isReverse(s1) && isReverse(s2)) {
                    ans = true;
                    break;
                }
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int isRange(string s, string range) {
    for (int i = 0; i < s.length(); ++i) {
        char ch = s[i];
        int j = 0;
        for (j=0; j<range.length(); ++j) {
            if (ch == range[j]) {
                break;
            }
        }
        if (j == range.length()) return 0;
    } 
    return 1;
}

int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        cout << isRange(s, "01") << " " 
             << isRange(s, "01234567") << " " 
             << isRange(s, "0123456789") << " " 
             << isRange(s, "0123456789ABCDEF") << endl;
    }
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, v[10010], tot;
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        tot = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            tot += v[i];
        }
        int cnt = 0;
        bool ans = false;
        for (int i = 0; i < n && cnt*2<tot; ++i) {
            cnt += v[i];
            if (cnt*2 == tot) {
                ans = true;
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

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

int ans = -1;
int x;
int main() {
    cin >> x;
    for (int i = 1; i < 2048; ++i) {
        if ((x & i) + (x | i) == 2025) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], b[MAXN];

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

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], b[MAXN], s[MAXN];

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

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    // 初始化
    for (int i = 1; i<=n; ++i) {
        b[i] = s[i] - s[i-lowbit(i)];
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

/**
 * 差分：
 *  - 假设 A 序列为原序列
 *  - 差分数列 C 为原序列每两个数之间的差
 *    - 即：c[i] = a[i] - a[i-1]
 *         c[1] = a[1]
 *         c[2] = a[2] - a[1]
 *         c[3] = a[3] - a[2]
 *  - 所以：
 *    - a[i] = sum(c[1]+c[2]+...c[i])
 * 
 * 对于本题，如果把数组变成差分数组：
 *  - [x,y] 每个数加上 k，等价于:
 *    - c[x] += k
 *    - c[y+1] -= k
 *  - 求第 a[x] 的值，等价于：
 *    - sum(c[1]+c[2]+...c[x])
 *    - 即求前缀和
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], c[MAXN], b[MAXN];

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

void add(int idx, int v) {
    while (idx <= n) {
        b[idx] += v;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c[i] = a[i] - a[i-1];
        add(i, c[i]);
    }
    while (m--) {
        int op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y+1, -k);
        } else {
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      c[i][j] += v;
    }
  }
}

int query(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

struct Node {
    int v;
    int origin_idx;
    int next_idx;
};

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

#define MAXN (int)(5*1e5+10)

struct Node {
    int v;
    int origin_idx;
    int next_idx;
};
Node a[MAXN];
int n,c[MAXN];
long long ans;

bool comp1(const Node &a, const Node &b) {
    return a.v < b.v;
}

bool comp2(const Node &a, const Node &b) {
    return a.origin_idx < b.origin_idx;
}

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

void add(int a, int v) {
    while (a<=n) {
        c[a]+=v;
        a+=lowbit(a);
    }
}

int query(int a) {
    int ret = 0;
    while(a) {
        ret += c[a];
        a -= lowbit(a);
    }
    return ret;
}


int main() {
    cin >> n;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i].v;
        a[i].origin_idx = i;
    }
    stable_sort(a+1, a+1+n, comp1);
    for (int i = 1; i<=n; ++i) 
        a[i].next_idx = i;
    stable_sort(a+1, a+1+n, comp2);

    for (int i = 1; i <=n; ++i) {
        add(a[i].next_idx, 1);
        ans += i - query(a[i].next_idx);
    }
    cout << ans << endl;

    return 0;
}

/**
 * 数状数组求逆序对。
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN int(3e5+10)

int n, b[MAXN];
long long ans;

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

void add(int idx, int v) {
    while (idx <= n) {
        b[idx] += v;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); 
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        // 将学号下标从 0 开始改到 1 开始
        a = a + 1;
        ans += query(a - 1);
        add(a, 1);
    }      
    cout << ans << endl;
    return 0;
}

void dfs(int pt) // pt 表示层数
{
    if (终止条件) {
        // 处理
        return;
    }
    for (枚举这个层的所有可选项) {
        if（这个选项是合法的）{
            标记这个选项（保存现场）
            dfs(pt+1); 
            取消标记（恢复现场）
        }
    }
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int dfs(int x) {
    int test[9] = {0};
    cout << x << endl;
    dfs(x + 1);
    return 0;
}

int main() {
    dfs(0);
    return 0;
}

bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int v[15], ans;
bool flag[15];

bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

void dfs(int pt) {
    if (pt == n) {
        ans++;
        if (ans <= 3) {
            for (int i = 0; i < n; i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i]==false) {
            flag[i] = true;
            v[pt] = i;
            if (check(pt)) dfs(pt + 1);
            flag[i] = false;
        }
    }
    
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, k, tot, ans;
int a[22], p[22];

bool isPrime(int v) {
    for (int i = 2; i*i <= v; ++i) {
        if (v%i == 0) {
            return false;
        }
    }
    return true;
}

void dfs(int pt) {
    if (pt == k+1) {
        if (isPrime(tot)) {
            ans++;
        }
    } else {
        // 每一层都必须取比前一层更大的下标，防止重复取
        for (int i = p[pt-1]+1; i <= n; ++i) {
            p[pt] = i;
            tot += a[i];
            dfs(pt+1);
            tot -= a[i];
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
int n, m;
char tu[105][105];
int ans;
int movex[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int movey[8] = {1, -1, 0, 0, 1, -1, 1, -1};

void dfs(int x, int y) {
    tu[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int nx = x + movex[i];
        int ny = y + movey[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m 
            || tu[nx][ny] != 'W') continue;
        dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tu[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tu[i][j] == 'W') {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int s[11], b[11], v[11];
int ans = INT_MAX;

/**
 * pt: 当前处理到的食材
 * cnt: 当前选中的食材数量
 * ss: 当前选中的食材的总酸度
 * bb: 当前选中的食材的总甜度
 */
void dfs(int pt, int cnt, int ss, int bb) {
    if (pt == n) {
        if (cnt > 0) {
            ans = min(ans, abs(ss - bb));
        }
        return;
    }
    v[pt] = 1;
    dfs(pt + 1, cnt + 1, ss * s[pt], bb + b[pt]);
    v[pt] = 0;
    dfs(pt + 1, cnt, ss, bb);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> b[i];
    }
    dfs(0, 0, 1, 0);
    cout << ans << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int row_cnt[6][2], col_cnt[6][2];
char tu[7][7], mark[7][7];

bool check(int r, int c) {
    // 在每一行和每一列中，黑色棋子和白色棋子的数量必须相等（即为 3）
    if (row_cnt[r][1] > 3 || row_cnt[r][0] > 3 || col_cnt[c][1] > 3 || col_cnt[c][0] > 3) return false;
    
    // 不能有超过两个相同颜色的棋子连续排列
    if (r >= 2) {
        if (tu[r][c] == '1' && tu[r-1][c] == '1' && tu[r-2][c] == '1') return false;
        if (tu[r][c] == '0' && tu[r-1][c] == '0' && tu[r-2][c] == '0') return false;
    }
    if (c >= 2) {
        if (tu[r][c] == '1' && tu[r][c-1] == '1' && tu[r][c-2] == '1') return false;
        if (tu[r][c] == '0' && tu[r][c-1] == '0' && tu[r][c-2] == '0') return false;
    }
    return true;
}

// 行列唯一性检查
bool final_check() {
    set<int> row_set, col_set;
    for (int i = 0; i < 6; i++) {
        int v = 0;
        for (int j = 0; j < 6; ++j) {
            v = v * 10 + (tu[i][j] - '0');
        }    
        row_set.insert(v);
    }
    if (row_set.size() != 6) return false;
    for (int j = 0; j < 6; ++j) {
        int v = 0;
        for (int i = 0; i < 6; ++i) {
            v = v * 10 + (tu[i][j] - '0');
        }
        col_set.insert(v);
    }
    if (col_set.size() != 6) return false;
    return true;
}

void dfs(int r, int c);
void try_dfs(int r, int c) {
    char ch = tu[r][c];
    row_cnt[r][ch - '0']++;
    col_cnt[c][ch - '0']++;
    if (check(r, c)) {
        int nr = r;
        int nc = c + 1;
        if (nc == 6) {
            nr++;
            nc = 0;
        }
        dfs(nr, nc);
    }
    row_cnt[r][ch - '0']--;
    col_cnt[c][ch - '0']--;
}

void dfs(int r, int c) {
    if (r == 6) {
        if (final_check()) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 6; j++) {
                    cout << tu[i][j];
                }
            }
            cout << endl;
            // 因为只有一个合法解，所以找到答案就退出
            exit(0);
        }
        return;
    }
    
    if (mark[r][c] == 0) {
        tu[r][c] = '1';
        try_dfs(r, c);
        tu[r][c] = '0';
        try_dfs(r, c);
    } else {
        tu[r][c] = mark[r][c];
        try_dfs(r, c);
    }
}

void init() {
    memset(mark, 0, sizeof(mark));
    mark[0][0] = '1';
    mark[0][1] = '0';
    mark[0][3] = '0';
    mark[1][3] = '0';
    mark[2][4] = '0';
    mark[2][5] = '0';
    mark[4][2] = '1';
    mark[4][5] = '1';
    mark[5][1] = '0';
    mark[5][4] = '1';
}

int main() {
    init();
    dfs(0, 0);
    return 0;
}

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

// 0 - 空地
// 1 - 障碍物
int tu[6][6], n, m, t, sx, sy, ex, ey, ans;

int movex[]={1,-1,0,0};
int movey[]={0,0,-1,1};

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        ans++;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int tox = x + movex[i];
        int toy = y + movey[i];
        if (tox >=1 && tox<=n && toy>=1 && toy<=m && tu[tox][toy]!=1){
            tu[tox][toy]=1;
            dfs(tox, toy);
            tu[tox][toy]=0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> t;
    cin >> sx >> sy >> ex >> ey;
    while (t--) {
        int x, y;
        cin >> x >> y;
        tu[x][y] = 1;
    }
    tu[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, tot, v[10];

void dfs(int pt) {
    if (tot == n) {
        cout << v[1];
        for (int i = 2; i < pt; ++i) {
            cout << "+" << v[i];
        }
        cout << endl;
        return;
    }
    for (int i = v[pt-1]; tot + i <=n && i < n ; ++i) {
        tot += i;
        v[pt] = i;
        dfs(pt+1);
        tot -= i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    v[0] = 1;
    dfs(1);
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, a[100010], b[100010];

int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) 
            cin >> a[i];
        for (int i = 0; i < n; ++i) 
            cin >> b[i];
        stack<int> q;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            q.push(a[i]);
            while (!q.empty() && q.top() == b[idx]) {
                q.pop();
                idx++;
            }
        }
        if (q.empty()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    int m, n, t, ans = 0;
    cin >> m >> n;
    vector<int> v; 
    while (cin >> t) {
        if (find(v.begin(), v.end(), t) == v.end()) { // 如果不在内存中
            v.push_back(t); 
            ++ans;
        }
        if (v.size() > m) 
            v.erase(v.begin());
    }
    cout << ans << endl;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

stack<int> s;
int a, v1, v2;

int main() {
    char ch;
    while (cin >> ch) {
        if (ch == '@') break;
        if (ch >= '0' &&  ch <='9') {
            a = a*10 + ch - '0';
        } else if (ch == '.') {
            s.push(a);
            a = 0;
        } else if (ch == '+') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 + v2);
        } else if (ch == '-') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 - v1);
        } else if (ch == '*') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 * v2);
        } else if (ch == '/') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 / v1);
        }
    }
    cout << s.top() << endl;
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int t;
    int len;
    vector<int> v;
};

// 桶，记录每个国家的乘客数量
int cnt[100010], n, t, ans;
// 队列
queue<Node> q;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        Node a;
        cin >> a.t >> a.len;
        a.v.resize(a.len);
        for (int j = 0; j < a.len; ++j) {
            cin >> a.v[j];
            if (cnt[a.v[j]] == 0) ans++;
            cnt[a.v[j]]++;
        }
        q.push(a);
        int min_t = a.t - 86400;
        // 检查出列
        a = q.front();
        while (a.t <= min_t) {
            for (int j = 0; j < a.len; ++j) {
                cnt[a.v[j]]--;
                if (cnt[a.v[j]] == 0) ans--;
            }
            q.pop();
            a = q.front();
        }
        cout << ans << endl;
    }
    return 0;
}

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

set<int> s;
int n, x, ans;
bool debug = false;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> x;
    ans = x;
    s.insert(x);
    for (int i = 1; i < n; ++i) {
        cin >> x;
        set<int>::iterator it;
        it = s.lower_bound(x);
        if (it != s.end() && *it == x) {
            continue;
        } else {
            int diff = INT_MAX;
            if (it != s.end()) {
                diff = min(diff, abs(*it-x));
            }
            if (it != s.begin()) {
                it--;
                diff = min(diff, abs(*it-x));
            }
            ans += diff;
            s.insert(x);
        }
    }
    cout << ans << endl;
    return 0;
}