/*
(In the name of Allah, the Most Gracious, the Most Merciful)
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <utility>
#include <vector>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define endl "\n"
#define sz(x) (int) (x).size()
#define vi vector<int>
#define ll long long
#define db double
#define pi pair<int, int>
#define F first
#define Sc second
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mx(v) *max_element(v.begin(),v.end())
#define mn(v) *min_element(v.begin(),v.end())
#define sum(v) accumulate(v.begin(),v.end(),0)
#define uni(v) v.erase(unique(v.begin(),v.end()),v.end());
#define sum(v) accumulate(v.begin(),v.end(),0)
#define test() int _; cin >> _; while(_--)
#define gcd(a,b) __gcd(a,b);
#define lcm(a,b) (a/(gcd(a,b))*b);
#define me(a, x) memset(a, x, sizeof(a))
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
const int MOD = (int)1e9 + 7; // 998244353;
const int MX = (int)2e5 + 5;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
LyoKICAgIChJbiB0aGUgbmFtZSBvZiBBbGxhaCwgdGhlIE1vc3QgR3JhY2lvdXMsIHRoZSBNb3N0IE1lcmNpZnVsKQogICAgCgogICAgCiovCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxhcnJheT4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxudW1lcmljPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxyYW5kb20+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSByZXAoaSxhLG4pIGZvciAoaW50IGk9YTtpPG47aSsrKQojZGVmaW5lIHBlcihpLGEsbikgZm9yIChpbnQgaT1uLTE7aT49YTtpLS0pCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgc3ooeCkgKGludCkgKHgpLnNpemUoKQojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+IAojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGRiIGRvdWJsZQojZGVmaW5lIHBpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFNjIHNlY29uZAojZGVmaW5lIGJnKHgpIGJlZ2luKHgpCiNkZWZpbmUgYWxsKHgpIGJnKHgpLCBlbmQoeCkKI2RlZmluZSByYWxsKHgpIHgucmJlZ2luKCksIHgucmVuZCgpCiNkZWZpbmUgc29yKHgpIHNvcnQoYWxsKHgpKQojZGVmaW5lIHJzeiByZXNpemUKI2RlZmluZSBpbnMgaW5zZXJ0CiNkZWZpbmUgZnQgZnJvbnQoKQojZGVmaW5lIGJrIGJhY2soKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGViIGVtcGxhY2VfYmFjawojZGVmaW5lIHBmIHB1c2hfZnJvbnQKI2RlZmluZSBteCh2KSAqbWF4X2VsZW1lbnQodi5iZWdpbigpLHYuZW5kKCkpCiNkZWZpbmUgbW4odikgKm1pbl9lbGVtZW50KHYuYmVnaW4oKSx2LmVuZCgpKQojZGVmaW5lIHN1bSh2KSBhY2N1bXVsYXRlKHYuYmVnaW4oKSx2LmVuZCgpLDApCiNkZWZpbmUgdW5pKHYpIHYuZXJhc2UodW5pcXVlKHYuYmVnaW4oKSx2LmVuZCgpKSx2LmVuZCgpKTsKI2RlZmluZSBzdW0odikgYWNjdW11bGF0ZSh2LmJlZ2luKCksdi5lbmQoKSwwKQojZGVmaW5lIHRlc3QoKSBpbnQgXzsgY2luID4+IF87IHdoaWxlKF8tLSkKI2RlZmluZSBnY2QoYSxiKSBfX2djZChhLGIpOwojZGVmaW5lIGxjbShhLGIpIChhLyhnY2QoYSxiKSkqYik7CiNkZWZpbmUgbWUoYSwgeCkgbWVtc2V0KGEsIHgsIHNpemVvZihhKSkKI2RlZmluZSB5ZXMgY291dCA8PCAieWVzIiA8PCBlbmRsCiNkZWZpbmUgbm8gY291dCA8PCAibm8iIDw8IGVuZGwKI2RlZmluZSBZZXMgY291dCA8PCAiWWVzIiA8PCBlbmRsCiNkZWZpbmUgTm8gY291dCA8PCAiTm8iIDw8IGVuZGwKI2RlZmluZSBZRVMgY291dCA8PCAiWUVTIiA8PCBlbmRsCiNkZWZpbmUgTk8gY291dCA8PCAiTk8iIDw8IGVuZGwKCmNvbnN0IGludCBNT0QgPSAoaW50KTFlOSArIDc7IC8vIDk5ODI0NDM1MzsKY29uc3QgaW50IE1YID0gKGludCkyZTUgKyA1OwoKCmludCBtYWluKCl7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwogICAgCiAgICAKfQ==