#include #define pb push_back using namespace std; typedef long long LL; const int S = 100003; const int MOD = 1e9+7; const double pi = 2 * acos (0.0); int _In(){int x; scanf("%d", &x); return x;} LL _LLI(){LL x; scanf("%lf", &x); return x;} int dirX[]={1, 0, -1, 0, 1, -1, 1, -1}; int dirY[]={0, 1, 0, -1, 1, -1, -1, 1}; int rX[] = {1, 1, 2, 2, -1, -1, -2, -2}; int rY[] = {2, -2, 1, -1, 2, -2, 1, -1}; template T Distance(T x1, T y1, T x2, T y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}; int sset(int N, int pos){return N=N|(1<