#include <bits/stdc++.h>
#define gc getchar
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define rep2(i, a, b) for(int i=a;i>=b;--i)
#define wipe(a, b) memset(a, b, sizeof a);
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
inline int scan(){
int n=0, x=gc(), s=1;
for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;
for(;x>='0'&&x<='9';x=gc()) n = 10*n + x - '0';
return n*s;
}
int gcd(int a, int b){
return (b?gcd(b, a%b):a);
}
int main(){
ios::sync_with_stdio(false), cin.tie(0);
return 0;
}
