jacky860226

#ifndef TREAP
#define TREAP
template<typename T>
class treap{
	private:
		struct node{
			T data;
			unsigned fix;
			int size;
			node *ch[2];

jacky860226

#include<algorithm>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
template<typename T>
inline string to_string(const T& x){

jacky860226

namespace std{
	inline int __lg(int n){//Precondition: n >= 0
		int k=0;
		for(;n!=0;n>>=1)++k;
		return k?--k:1;
	}
}

jacky860226

#ifndef KOREA_TREE
#define KOREA_TREE
template<typename T>
class korea_tree{
	private:
		struct node{
			node *ch[2];
			T data;
			int s;
			node(const T&d):data(d),s(1){}

jacky860226

#ifndef SUNMOON_DOUBLE
#define SUNMOON_DOUBLE
#include <cmath>
#include <iostream>
const double EPS = 1e-9;
struct Double {
  double d;
  Double(double d = 0) : d(d) {}
  Double operator-() const { return -d; }
  Double operator+(const Double &b) const { return d + b.d; }

jacky860226

#ifndef SUNMOON_DYNEMIC_KD_TREE
#define SUNMOON_DYNEMIC_KD_TREE
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
template<typename T,size_t kd>//kd表示有幾個維度 
class kd_tree{
	public:
		struct point{

jacky860226

#ifndef SUNMOON_MERSENNE_TWISTER
#define SUNMOON_MERSENNE_TWISTER
template<typename T,T w,int n,T m,T r,T a,T u,T d,T s,T b,T t,T c,T l,T f>
class mersenne_twister{
	private:
		int index;
		const T lower_mask=(1ull<<r)-1ull;
		const T upper_mask=~lower_mask;
		T mt[n];
		inline void twist(){

jacky860226

#ifndef SUNMOON_SUBTRACT_WITH_CARRY
#define SUNMOON_SUBTRACT_WITH_CARRY
template<typename T,T w,int s,int r>
class subtract_with_carry{
	private:
		int index;
		T x[r],cy,mask;
	public:
		subtract_with_carry(T seed):index(0),cy(0),mask((1ll<<w)-1ll){
			for(int i=0;i<r;++i){

jacky860226

#ifndef REFERENCE_POINTER
#define REFERENCE_POINTER
template<typename T>
struct _RefCounter{
	T data;
	int ref;
	_RefCounter(const T&d=0):data(d),ref(0){}
};
template<typename T>
struct reference_pointer{

jacky860226

#include<string.h>
#include<limits.h>
#include<vector>
#include<queue>
#include<algorithm>
template<typename T>
struct DINIC{
	static const int MAXN=105;
	static const T INF=INT_MAX;
	int n;/*點數*/