1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
template<typename T> void println(const T &t) { cout << t << '\n'; }
template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); }
template<typename T> void print(const T &t) { cout << t << ' '; }
template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t; print(rest...); }
// this overload is chosen when there's only one argument
template<class T> void scan(T &t) { cin >> t; }
template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); }
using ll = long long;
using vl = vector<ll>;
using vi = vector<int>;
#define rng(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(n) for(int _ = 0, __ = (int)n; _ < __; _++)
#define stp(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define FOR(x, cont) for (auto &x: cont)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define SZ(x) (int)(x).size()
#define pq(T,COMP) priority_queue<T, vector<T>, COMP>
#define popcnt(x) __builtin_popcount((x))
auto bet = [](const ll x, const ll y, const ll i) {
    return x <= i && i <= y;
};
using pii = pair<int,int>;
using vb = vector<bool>;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX