#include using namespace std; // #define int long long using ll= long long; #define fo(i,b) for(int i = (0); i < (b); ++i) #define f(i,a,b) for(int i = (a); i < (b); ++i) #define rep(i,a,b) for(int i = (a); i < (b); ++i) typedef pair pii; typedef vector vi; const int NMAX = 112345; const int PMAX = 17; bool valid[1<