template.cpp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;
//using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

string to_string(string s){
	return '"' + s + '"';
}

string to_string(const char* s){
	return to_string((string)s);
}

string to_string(bool b){
	return b ? "true" : "false";
}

template<typename t1, typename t2>
string to_string(pair<t1, t2> t){
	return "{" + to_string(t.first) + ", " + to_string(t.second) + "}";
}

template<typename T>
string to_string(vector<T> v){
	string res = "{";
	for(int i=0; i<v.size(); i++){
		res += to_string(v[i]);
		if(i == v.size()-1) res += "}";
		else res += ", ";
	}
	return res;
}

template<typename T>
string to_string(queue<T> q){
	string res = "{";
	while(q.size()){
		T now = q.front(); q.pop();
		res += to_string(now);
		if(q.size()) res += ", ";
		else res += "}";
	}
	return res;
}

template<typename T>
string to_string(stack<T> stk){
	string res = "{";
	vector<T> v;
	while(stk.size()){
		v.push_back(stk.top()); stk.pop();
	}
	reverse(v.begin(), v.end());
	return to_string(v);
}

template<typename T>
string to_string(deque<T> v){
	string res = "{";
	for(int i=0; i<v.size(); i++){
		res += to_string(v[i]);
		if(i == v.size()-1) res += "}";
		else res += ", ";
	}
	return res;
}

void debug_out(){
	cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << " " << to_string(H);
	debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] : ", debug_out(__VA_ARGS__)
#else
#define debug(...) 917
#endif

const int di[] = {1, 0, -1, 0, 1, 1, -1, -1}, dj[] = {0, 1, 0, -1, 1, -1, 1, -1};
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
ll inv(ll a, ll m){ //return x when ax mod m = 1, fail -> -1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
void finish(){ exit(0); }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

}