// 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;
}
Ly8gQXV0aG9yOiBwcHBzc3NsYwovLyBEYXRlOiAxNS8wOC8yMDI2CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGU8Y2xhc3MgWCwgY2xhc3MgWT4gdm9pZCBtaW5pKFggJngsIGNvbnN0IFkgJnkpewoJeCA9IG1pbih4LCB5KTsKfQoKdGVtcGxhdGU8Y2xhc3MgWCwgY2xhc3MgWT4gdm9pZCBtYXhpKFggJngsIGNvbnN0IFkgJnkpewoJeCA9IG1heCh4LCB5KTsKfQoKdHlwZWRlZiBzdHJpbmcgc3RyOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIF9faW50MTI4IGkxMjg7CnR5cGVkZWYgZG91YmxlIGRiOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwp0eXBlZGVmIHBhaXI8bGQsIGxkPiBwbGRsZDsKdHlwZWRlZiBwYWlyPGRiLCBkYj4gcGRkOwp0eXBlZGVmIHBhaXI8Y2hhciwgY2hhcj4gcGNjOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmw7CnR5cGVkZWYgdmVjdG9yPGNoYXI+IHZjOwp0eXBlZGVmIHZlY3RvcjxwaWk+IHZwaWk7CnR5cGVkZWYgdmVjdG9yPHBsbD4gdnBsbDsKdHlwZWRlZiB2ZWN0b3I8dmVjdG9yPGludD4+IHZpaTsKdHlwZWRlZiB2ZWN0b3I8dmVjdG9yPGxsPj4gdmxsOwp0eXBlZGVmIHZlY3Rvcjx2ZWN0b3I8Y2hhcj4+IHZjYzsKdHlwZWRlZiBtYXA8aW50LCBpbnQ+IG1waWk7CnR5cGVkZWYgbWFwPGxsLCBsbD4gbXBsbDsKdHlwZWRlZiBzZXQ8aW50PiBzaTsKdHlwZWRlZiBzZXQ8bGw+IHNsOwp0eXBlZGVmIGNvbXBsZXg8bGQ+IGNkOwoKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIFJlcChpLCBsLCByLCB4KSBmb3IoaW50IGkgPSBsOyBpIDwgKGludClyOyBpICs9IHgpCiNkZWZpbmUgUmVwZChpLCBsLCByLCB4KSBmb3IoaW50IGkgPSBsOyBpID4gKGludClyOyBpIC09IHgpCiNkZWZpbmUgRm9yKGksIGwsIHIsIHgpIGZvcihpbnQgaSA9IGw7IGkgPD0gKGludClyOyBpICs9IHgpCiNkZWZpbmUgRm9yZChpLCBsLCByLCB4KSBmb3IoaW50IGkgPSBsOyBpID49IChpbnQpcjsgaSAtPSB4KQojZGVmaW5lIEZvcmUoeCwgYSkgZm9yKGF1dG8geDogYSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBwZiBwdXNoX2Zyb250CiNkZWZpbmUgcHBiIHBvcF9iYWNrCiNkZWZpbmUgcHBmIHBvcF9mcm9udAojZGVmaW5lIGlucyBpbnNlcnQKI2RlZmluZSBlcmEgZXJhc2UKI2RlZmluZSB1cGIgdXBwZXJfYm91bmQKI2RlZmluZSBsd2IgbG93ZXJfYm91bmQKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpLCBhLmVuZCgpCgpjb25zdCBkYiBQSSA9IGFjb3MoLTEpOwpjb25zdCBsbCBpbmYgPSAxZTE4ICsgMTsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBtYXhuID0gMWU1ICsgNTsKCnNpZ25lZCBtYWluKCl7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUobnVsbHB0cik7IGNvdXQudGllKG51bGxwdHIpOwoJCgljZXJyIDw8ICJUSU1FIEVMQVBTRUQ6ICIgPDwgMS4wICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDIDw8ICJzLlxuIjsKCXJldHVybiAwOwp9