#include<bits/stdc++.h>
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define mset(x, y) memset(x, y, sizeof(x))
#define SZ(x) int(x.size())
#define db(x) cerr<<(#x)<<'='<<(x)<<endl
#define db2(x,y) cerr<<(#x)<<'='<<(x)<<' '<<(#y)<<'='<<(y)<<endl
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> vi;
typedef vector<PII> vpi;
typedef vector<vi> vvi;
typedef long long LL;
typedef vector<LL> vll;
typedef vector<vll> vvll;
typedef pair<LL, LL> pll;
typedef double ld;

int main() {
    cin.tie(0) -> sync_with_stdio(false);
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}