// Author: pppssslc
// Date: 15/08/2026
#include<bits/stdc++.h>

using namespace std;

template<class X, class Y> void mini(X &x, const Y &y){
	x = min(x, y);
}

template<class X, class Y> void maxi(X &x, const Y &y){
	x = max(x, y);
}

typedef string str;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pldld;
typedef pair<db, db> pdd;
typedef pair<char, char> pcc;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<char> vc;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> vll;
typedef vector<vector<char>> vcc;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;
typedef set<int> si;
typedef set<ll> sl;
typedef complex<ld> cd;

#define se second
#define fi first
#define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
#define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
#define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
#define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
#define Fore(x, a) for(auto x: a)
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ins insert
#define era erase
#define upb upper_bound
#define lwb lower_bound
#define all(a) a.begin(), a.end()

const db PI = acos(-1);
const ll inf = 1e18 + 1;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cerr << "TIME ELAPSED: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
	return 0;
}