#include <bits/stdc++.h>

#define getint(n) int n; scanf("%d%*c", &n)
#define getll(n) long long n; scanf("%lld%*c", &n)
#define getchar(n) char n; scanf("%c%*c", &n);
#define intab getint(a); getint(b)
 
#define forr(i, n) for(int i=1;i<=(n);i++)
#define fors(i, s, e) for(int i=(s); i<=(e); i++)
#define fore(i, e, s) for(int i=(e); i>=(s); i--)

#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back

using namespace std;
using ll = long long;        using lll = __int128_t;
using pii = pair<int,int>;   using pll = pair<ll,ll>;
using vi = vector<int>;      using vl = vector<ll>;
using vii = vector<pii>;     using vll = vector<pll>;