#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long typedef long long type; #define PI 3.1415926535897932626 using namespace std; //type gcd(type a, type b) {return b == 0 ? a : gcd(b, a % b);} int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}