#include using namespace std; //#define int long long #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define rep(i,n) for(int i=0;i vi; typedef vector vc; typedef vector vb; typedef vector vd; typedef vector vs; typedef vector > vpii; typedef vector > vvi; typedef vector > vvc; typedef vector > vvb; typedef vector > vvd; typedef vector > vvs; typedef vector vl; typedef vector > vvl; typedef vector > > vvvl; ll MOD = 1000000007; const long long L_INF = 1LL << 60; const int INF = 2147483647; // 2^31-1 const double PI = acos(-1); //cout< inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;} template inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;} template void debug(T v){rep(i,v.size()) cout<> n; cout << 1 << " " << n << endl; }