1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <sstream>
#include <map>
#include <bitset>
#include <ctime>
#include <unordered_map>
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define PI acos(-1.0)
#define LL long long
#define ULL unsigned long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define PII pair<int,int>
#define PDD pair<double,double>
#define MP make_pair
#define scan(x) scanf("%d",&x)
#define sqr(x) ((x)*(x))
template <class T>
inline void rd(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar();
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}
template <class T> void Out(T a) { if(a < 0){putchar('-');a = -a;}if(a >= 10)Out(a / 10);putchar(a % 10 + '0');  }  
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX