[Dr.Lib]Note:Algorithms – LLRB——红黑树的现代实现

Via http://www.cnblogs.com/Seiyagoo/archive/2013/10/13/3366290.html

一、本文内容

以一种简明易懂的方式介绍红黑树背后的逻辑实现2-3-4树，以及红黑树的插入、删除操作，重点在2-3-4树与红黑树的对应关系上，并理清红黑树相关操作的来龙去脉。抛弃以往复杂的实现，而分析红黑树的一种简单实现LLRB。

二、算法应用

红黑树，给人以强烈的第一听觉冲击力——红与黑，好像很高端的感觉。事实上的确如此，红黑树是一种高级数据结构，在C++、Java的标准库里作为set、map的底层数据结构实现，以及linux中进程的公平调度。

三、2-3-4树

标题是红黑树，为什么讲2-3-4树？因为红黑树就是2-3-4树的一种等价形式，更准确地来说，我们用红黑树来完成2-3-4树的各种操作（如插入、删除）。原因就是2-3-4树的实现即维护太麻烦。所以理解2-3-4树才能真正理解红黑树。而历史就是这么发展的，了解过去，现在的一切才有了意义。算法导论关于红黑树这一节就忽略了这一点，让人知其然而不知其所以然。

OK，暂时先忽略复杂的红黑树，从简单的2-3-4树开始。

1、定义

2-3-4树是一种泛化的BST，它的每个结点允许1,2或者3个键(key)，那么对应的有三种结点：

2-node：一个key，两个孩子；

3-node：二个key，三个孩子；

4-node：三个key，四个孩子。

注：k-node表示有k个链接（link）。泛化的BST还有2-3树，B树等。

从图中可以看出2-3-4树的另一个性质：它是完全平衡的（等高），即从根结点到叶子结点距离相等。

2、插入操作

2-3-4树本身就是一种查找树（中序遍历有序），故其查找操作同二叉查找。

2-3-4树的插入操作类似二叉查找树，先是查找操作失败（从根结点查找到叶子结点），然后在底部的叶子结点插入。

因为2-3-4树的结点有三种类型，所以操作有点差异。对于2-node和3-node，分别直接插入可变成3-node，4-node；但是对于4-node若直接插入则违反了定义。在4-node插入之前，先分裂4-node成2个2-node，再将待插入的key插入对应的2-node。如下图，H查找失败，在H插入4-node（由三个key F、G、J组成）之前，先对该4-node分裂（将三个key的中间值提上父节点，剩余的二个key分别作为中间key的左右孩子），然后再将H插入2-node J中。这样操作的结果是查找到达底部叶子结点时，始终是2-node或者3-node。

插入算法思想：自下而上的算法由原作者Bayer在1972年提出，自上而下的算法由Guibas-Sedgewick（红黑树这个名字来源于他们）在1978年提出，然后30年后也就是2008年Sedgewick教授又改进了红黑树的操作，也就是后面要介绍的LLRB。

自上而下的算法思路是，从根结点向下的查找过程中，遇到4-node就分裂，最后在底部的叶子结点插入。

那么为什么遇到4-node就分裂呢？4-node不是2-3-4树的一种合法结点类型吗？

答案可以从后面LLRB的算法思路可以得出。

因为遇到4-node就分裂就保证了当前结点不是4-node，则分裂孩子的4-node有两种情形：

分裂4-node的case 1

分裂4-node的case 2

注：上面的变换在树中任意位置都成立。

下面两张图是完整的插入过程（只有分裂结点类型为4-node的根结点才会导致树高增1）：

3、平衡性分析

2-3-4树的树高在最坏情况下为lgN（所有结点都是2-node型），最好情况下为lg4 N = 1/2 lgN（所有结点都是4-node型），2-3-4树的查找、插入操作都是lgN。

四、红黑树

终于到了高富帅——红黑树。。。

从2-3-4树的介绍可以看出，对2-node、3-node、4-node的不同数据类型进行转换，但所涉及的大部分任务使用这种直接的表示方法来实现并不方便。所以可以用

一种统一的方式完成转换，而只需很小的开销。这就是红黑树存在的意义，既有BST的标准搜索过程，又有2-3-4树的简单插入平衡过程。

下面介绍LLRB（Left-leaning red-black trees），而不是标准的红黑树。

1、定义

LLRB有三个特点：

（1）用BST来表示2-3-4树；

（2）用红边(红链接)来连接2-node来表示3-node和4-node（如下图）；

（3）3-node必须是向左倾斜的（两者的大者作为根）。

LLRB相对于标准的RB多了特点3，在标准的RB中右向倾斜的红链接是允许的。对于特点2，在物理上用一个bit（红或黑）来存储以表示指向该结点的红链接。

红链接来连接3-node或者4-node的内部key，而黑链接则连接外部的key；为了理解，可以消除红链接并将它们连接的结点都折叠起来（即将看做红链接连

接的点缩为一个点），则可以看出黑链接个数不变。

2-3-4树与红黑树是一一对应的关系

且上下关系中不允许2个连续的红边

由特点3可以推出LLRB的一个特性，红黑树与2-3-4树一一对应。

2、插入算法

同样地，在LLRB中查找操作同BST。

在插入之前要知道一个操作：旋转。它有两种情况：左旋，右旋。

左旋右旋

插入算法思路：即前面介绍的2-3-4树

具体实现时，插入一个结点时，始终是红结点，即用红边链接该结点。对于2-node、3-node直接插入（k-node有k个插入点），如违反上面的左红链接和连续的红链接，则旋转作调整。对于4-node（左右都为红链接），先分裂，物理实现是一个翻转（左右红链接变黑，父链接变红）。

2-node插入的两种case

3-node插入的三种case

4-node分裂操作

由4-node的分裂可知黑高度不变，分裂操作即翻转在图片上对应为红链接向上传递。

在介绍2-3-4树时，4-node分裂操作有两种情况，4-node的parent是2-node和3-node；再结合k-node有k个插入点，则总共有6种情况。

4-node的分裂case 1

4-node的分裂case 2

看了上面两幅图后，也许会让人觉得红黑树太复杂了，这么多case，其实不然，在LLRB实现中只有两种操作：旋转、翻转。旋转的目的是保持平衡，翻转的目的是分裂4-node。

看了下面的LLRB插入算法，你就会明白上面4-node的翻转、旋转其实是分开的两个过程（翻转自上而下，旋转自下而上），只是为了统一这个完整的过程而画在了一起，才会有那么多case。

LLRB的插入算法：

首先结合2-3-4树的插入算法思路，先从上至下查找（遇到4-node则翻转），然后在底部叶子结点插入，因为在从上至下的过程中，可能会产生不满足LLRB的性质的情况，故插入结点后需要从下至上调整以恢复LLRB性质。

下图是插入算法的核心代码，第2是分裂即翻转，第1是插入操作，第3、4是调整。

从插入算法可以看出，如果自下而上再分裂4-node，则会出现它的parent也可能是4-node，祖父结点也可能是4-node；我们可以一直向上分裂，这也正是上面提到的自上而下的思路；而更简单的方法是，在沿树向下的过程中，遇到4-node就分裂，这也正是自上而下与自下而上的区别。

插入算法的核心代码

上图的核心代码按照从上而下和从下而上的顺序放入BST的插入（递归版本）操作中即得到下图的完整的插入算法。

注：分裂（即翻转）是自上而下，所以放在递归之前；调整（即旋转）是自上而下，所以放在递归之后。

完整的插入代码

如果将分裂操作放到递归之后，也就是先自上而下查找，插入结点，然后自下而上调整也可同样完成插入操作而不破坏LLRB的性质。

2-3树的插入操作

其实上述描述的就是2-3树的插入操作，它与2-3-4树的插入的区别在于：2-3树先插入，再分裂（down）、调整（up）；2-3-4树先分裂（down），再插入、调整（up）。又因为插入总是在最后一层进行，故翻转的位置决定了对应树的实现。

这也是为什么2-3-4树叫top-down，而2-3树叫bottom-up。

3、删除算法

LLRB的删除类似于插入，只不过处理刚好相反。插入、删除都有临界点：插入4-node，删除2-node，对临界点的操作都会引起突变，因为它们会破坏LLRB的性质(黑高度)。

所以同插入一样，先从上至下查找，如果查找在3-node或4-node结束，则直接删除；

3-node和4-node的删除

对于2-node的删除同4-node的插入相反，2-node的删除是先合并2个2-node为1个4-node，然后再安全地删除对应的2-node中的key。

同样地，因为parent不为2-node（遇到即合并），再结合兄弟结点的2、3、4-node，则删除总共有6种情况。同样，实际的删除实现也

没这么复杂。

2-node的删除

在介绍删除任意一个结点时，先分析删除树中最小的结点。因为它是删除任意结点的一部分，后面可以看出来。

首先，为了保证可以直接删除最小的某个结点，需要假设当前结点h或者h.left是红色链。

然后从上而下查找过程中，2个2-node要变为1个4-node，则需反向翻转（红色父链接变黑，黑色子链接变红），

为了将红链从上向左子树传递（删除红结点，不改变黑高度），需保证h为红，h.left和h.left.left为黑；

当h.left和h.left.left都为黑时，

如果h.right.left为红，则要从右边借兄弟（下图case 2），如果h.right.left为黑，则不需要（下图case1）。

注：在翻转的同时，右子树可能会产生连续的红链，则需调整。

case 1

case 2

红链向左移动红链向左移动对应的example

deleteMin的实现

deleteMin的example

完成了deleteMin就完成了LLRB的删除操作的一大半。现在是删除LLRB的任意一个key，

自上而下查找过程中，左边查找用moveRedLeft；右边查找用moveRedRight；直到最后的底部叶子结点，直接删除即可；同样，自下而上调整。

怎样将delete操作归约到delteMin去呢？算法导论提供的一个技巧是：replace，deleteMin（即用后继的key代替当前的key，再删除右孩子的最小结点）。

删除技巧

完整删除代码

参考：

《算法导论》

《algorithm in c》

http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

[Dr.Lib]Note:Algorithms – 四边形不等式

若w[a,c]+w[b,d] \(\leq\) w[b,c]+w[a,d] (a<b<c<d)

则w满足凸四边形不等式

若w[i,j] \(\leq\) w[i,j] ([i,j]\(\subseteq\) [i',j'])

则w满足区间单调

2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n)

d满足凸四边形不等式 k[i,j-1] \(\leq\) k[i,j] \(\leq\) k[i+1,j]

w为凸 \(\Leftrightarrow\) w[i,j]+w[i+1,j+1] \(\leq\) w[i+1,j]+w[i,j+1]

1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1)

满足决策单调性，可用单调队列优化决策

[Dr.Lib]Note:Coding – 日常模板 Manual Ver-0.1

Via http://www.shuizilong.com/house/archives/%E6%97%A5%E5%B8%B8%E6%A8%A1%E6%9D%BF-manual-ver-0-1/

Orz岛娘……

/** Micro Mezz Macro Flation -- Overheated Economy ., Last Update: Aug. 20th 2013 **/ //{

/** Header .. **/ //{
#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define LOCAL
//#include "testlib.h"
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

//#include <tr1/unordered_set>
//#include <tr1/unordered_map>
//#include <array>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (int n____=(i=0,int(n));i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i>=a____;--i)

#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, nxt) for (int i=hd;i;i=nxt[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)
#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define BSC(A, x) (lower_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int((A).size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define Ts *this
#define rTs return Ts
#define fi first
#define se second
#define re real()
#define im imag()

#define Rush for(int ____T=RD(); ____T--;)
#define Display(A, n, m) {                      \
  REP(i, n){		                            \
        REP(j, m-1) cout << A[i][j] << " ";     \
        cout << A[i][m-1] << endl;		        \
	}						                    \
}
#define Display_1(A, n, m) {                    \
	REP_1(i, n){		                        \
        REP_1(j, m-1) cout << A[i][j] << " ";   \
        cout << A[i][m] << endl;		        \
	}						                    \
}

typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

template<class T> inline T& RD(T &);
template<class T> inline void OT(const T &);
//inline int RD(){int x; return RD(x);}
inline LL RD(){LL x; return RD(x);}
inline DB& RF(DB &);
inline DB RF(){DB x; return RF(x);}
inline char* RS(char *s);
inline char& RC(char &c);
inline char RC();
inline char& RC(char &c){scanf(" %c", &c); return c;}
inline char RC(){char c; return RC(c);}
//inline char& RC(char &c){c = getchar(); return c;}
//inline char RC(){return getchar();}

template<class T> inline T& RDD(T &);
inline LL RDD(){LL x; return RDD(x);}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}
template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}
template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}
template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}
template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}
inline char& RC(char &a, char &b){RC(a), RC(b); return a;}
inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}
inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}
inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}
inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}
inline void RS(char *s1, char *s2){RS(s1), RS(s2);}
inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}
template<class T0,class T1>inline void RDD(T0&a, T1&b){RDD(a),RDD(b);}
template<class T0,class T1,class T2>inline void RDD(T0&a, T1&b, T2&c){RDD(a),RDD(b),RDD(c);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void CLR(T &A){A.clear();}

template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}
template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(stack<T> &S){while (!S.empty()) S.pop();}

template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}
template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline bool EPT(T &a){return a.empty();}
template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}
template<class T, class C> inline T& SRT(T &A, C B){sort(ALL(A), B); return A;}
template<class T> inline T& RVS(T &A){reverse(ALL(A)); return A;}
template<class T> inline T& UNQQ(T &A){A.resize(unique(ALL(A))-A.begin());return A;}
template<class T> inline T& UNQ(T &A){SRT(A);return UNQQ(A);}

//}

/** Constant List .. **/ //{

const int MOD = int(1e9) + 7;
//int MOD = 99990001;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-12;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

//}

/** Add On .. **/ //{
// <<= '0. Nichi Joo ., //{
template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (a<b) a=b;}
template<class T> inline void checkMin(T &a, T &b, const T x){checkMin(a, x), checkMin(b, x);}
template<class T> inline void checkMax(T &a, T &b, const T x){checkMax(a, x), checkMax(b, x);}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}
inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

inline DB cos(DB a, DB b, DB c){return (sqr(a)+sqr(b)-sqr(c))/(2*a*b);}
inline DB cot(DB x){return 1./tan(x);};
inline DB sec(DB x){return 1./cos(x);};
inline DB csc(DB x){return 1./sin(x);};

//}
// <<= '1. Bitwise Operation ., //{
namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}
inline bool _1(LL x, int i){return bool(x&1LL<<i);}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);
    return x;
}

inline LL reverse_bits(LL x){
    x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
    x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
    x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
    x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
    x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);
    x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);
    return x;
}

template<class T> inline bool odd(T x){return x&1;}
template<class T> inline bool even(T x){return !odd(x);}
template<class T> inline T low_bit(T x) {return x & -x;}
template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}
template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}
template<class T> inline int cover_idx(T x){int p = 0; while (_1(p) < x ) ++p; return p;}

inline int clz(int x){return __builtin_clz(x);}
inline int clz(LL x){return __builtin_clzll(x);}
inline int ctz(int x){return __builtin_ctz(x);}
inline int ctz(LL x){return __builtin_ctzll(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}
inline int lg2(LL x){return !x ? -1 : 63 - clz(x);}
inline int low_idx(int x){return !x ? -1 : ctz(x);}
inline int low_idx(LL x){return !x ? -1 : ctz(x);}
inline int high_idx(int x){return lg2(x);}
inline int high_idx(LL x){return lg2(x);}
inline int parity(int x){return __builtin_parity(x);}
inline int parity(LL x){return __builtin_parityll(x);}
inline int count_bits(int x){return __builtin_popcount(x);}
inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}
// <<= '9. Comutational Geometry .,//{
namespace CG{

#define cPo const Po&
#define cLine const Line&
#define cSeg const Seg&

inline DB dist2(DB x,DB y){return sqr(x)+sqr(y);}

struct Po{
    DB x,y;Po(DB x=0,DB y=0):x(x),y(y){}

    void in(){RF(x,y);}void out(){printf("(%.2f,%.2f)",x,y);}
    inline friend istream&operator>>(istream&i,Po&p){return i>>p.x>>p.y;}
    inline friend ostream&operator<<(ostream&o,Po p){return o<<"("<<p.x<<", "<<p.y<< ")";}

    Po operator-()const{return Po(-x,-y);}
    Po&operator+=(cPo p){x+=p.x,y+=p.y;rTs;}Po&operator-=(cPo p){x-=p.x,y-=p.y;rTs;}
    Po&operator*=(DB k){x*=k,y*=k;rTs;}Po&operator/=(DB k){x/=k,y/=k;rTs;}
    Po&operator*=(cPo p){rTs=Ts*p;}Po&operator/=(cPo p){rTs=Ts/p;}
    Po operator+(cPo p)const{return Po(x+p.x,y+p.y);}Po operator-(cPo p)const{return Po(x-p.x,y-p.y);}
    Po operator*(DB k)const{return Po(x*k,y*k);}Po operator/(DB k)const{return Po(x/k,y/k);}
    Po operator*(cPo p)const{return Po(x*p.x-y*p.y,y*p.x+x*p.y);}Po operator/(cPo p)const{return Po(x*p.x+y*p.y,y*p.x-x*p.y)/p.len2();}

    bool operator==(cPo p)const{return!sgn(x,p.x)&&!sgn(y,p.y);};bool operator!=(cPo p)const{return sgn(x,p.x)||sgn(y,p.y);}
    bool operator<(cPo p)const{return sgn(x,p.x)<0||!sgn(x,p.x)&&sgn(y,p.y)<0;}bool operator<=(cPo p)const{return sgn(x,p.x)<0||!sgn(x,p.x)&&sgn(y,p.y)<=0;}
    bool operator>(cPo p)const{return!(Ts<=p);}bool operator >=(cPo p)const{return!(Ts<p);}

    DB len2()const{return dist2(x,y);}DB len()const{return sqrt(len2());}DB arg()const{return atan2(y,x);}
    Po&_1(){rTs/=len();}Po&conj(){y=-y;rTs;}Po&lt(){swap(x,y),x=-x;rTs;}Po&rt(){swap(x,y),y=-y;rTs;}
    Po&rot(DB a,cPo o=Po()){Ts-=o;Ts*=Po(cos(a),sin(a));rTs+=o;}
};

inline DB dot(DB x1,DB y1,DB x2,DB y2){return x1*x2+y1*y2;}
inline DB dot(cPo a,cPo b){return dot(a.x,a.y,b.x,b.y);}
inline DB dot(cPo p0,cPo p1,cPo p2){return dot(p1-p0,p2-p0);}
inline DB det(DB x1,DB y1,DB x2,DB y2){return x1*y2-x2*y1;}
inline DB det(cPo a,cPo b){return det(a.x,a.y,b.x,b.y);}
inline DB det(cPo p0,cPo p1,cPo p2){return det(p1-p0,p2-p0);}
inline DB ang(cPo p0,cPo p1){return acos(dot(p0,p1)/p0.len()/p1.len());}
inline DB ang(cPo p0,cPo p1,cPo p2){return ang(p1-p0,p2-p0);}
inline DB ang(cPo p0,cPo p1,cPo p2,cPo p3){return ang(p1-p0,p3-p2);}
inline DB dist2(const Po &a, const Po &b){return dist2(a.x-b.x, a.y-b.y);}
template<class T1, class T2> inline int dett(const T1 &x, const T2 &y){return sgn(det(x, y));}
template<class T1, class T2, class T3> inline int dett(const T1 &x, const T2 &y, const T3 &z){return sgn(det(x, y, z));}
template<class T1, class T2, class T3, class T4> inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(det(x, y, z, w));}
template<class T1, class T2> inline int dott(const T1 &x, const T2 &y){return sgn(dot(x, y));}
template<class T1, class T2, class T3> inline int dott(const T1 &x, const T2 &y, const T3 &z){return sgn(dot(x, y, z));}
template<class T1, class T2, class T3, class T4> inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(dot(x, y, z, w));}
template<class T1, class T2> inline DB arg(const T1 &x, const T2 &y){DB a=ang(x,y);return~dett(x,y)?a:2*PI-a;}
template<class T1, class T2, class T3> inline DB arg(const T1 &x, const T2 &y, const T3 &z){DB a=ang(x,y,z);return~dett(x,y,z)?a:2*PI-a;}
template<class T1, class T2, class T3, class T4> inline DB arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w){DB a=ang(x,y,z,w);return~dett(x,y,z,w)?a:2*PI-a;}
template<class T1, class T2> inline DB dist(const T1 &x, const T2 &y){return sqrt(dist2(x, y));}
template<class T1, class T2, class T3> inline DB dist(const T1 &x, const T2 &y, const T3 &z){return sqrt(dist2(x, y, z));}
inline Po _1(Po p){return p._1();}inline Po conj(Po p){return p.conj();}
inline Po lt(Po p){return p.lt();}inline Po rt(Po p){return p.rt();}
inline Po rot(Po p,DB a,cPo o=Po()){return p.rot(a,o);}
inline Po operator *(DB k,cPo p){return p*k;}
inline Po operator /(DB k,cPo p){return conj(p)*k/p.len2();}

typedef vector<Po> VP;

struct Line{
    Po a,b;Line(cPo a=Po(),cPo b=Po()):a(a),b(b){}
    Line(DB x0,DB y0,DB x1,DB y1):a(Po(x0,y0)),b(Po(x1,y1)){}
    Line(cLine l):a(l.a),b(l.b){}

    //Ax+By+C=0
    Line(DB A,DB B,DB C){
        C=-C;if(!::sgn(A))a=Po(0,C/B),b=Po(1,C/B);
        else if(!::sgn(B))a=Po(C/A,0),b=Po(C/A,1);
        else a=Po(0,C/B),b=Po(1,(C-A)/B);
    }

    void in(){a.in(),b.in();}
    inline friend istream&operator>>(istream&i,Line& p){return i>>p.a>>p.b;}
    inline friend ostream&operator<<(ostream&o,Line p){return o<<p.a<<"-"<< p.b;}

    Line operator+(cPo x)const{return Line(a+x,b+x);}
    Line operator-(cPo x)const{return Line(a-x,b-x);}
    Line operator*(DB k)const{return Line(a*k,b*k);}
    Line operator/(DB k)const{return Line(a/k,b/k);}

    Po operator*(cLine)const;
    Po d()const{return b-a;}DB len2()const{return d().len2();}DB len()const{return d().len();}DB arg()const{return d().arg();}

    int sgn(cPo p)const{return dett(a, b, p);}
    int sgn(cLine)const;

    bool sameSgn(cPo  p1,cPo  p2)const{return sgn(p1)==sgn(p2);}
    void getEquation(DB&K,DB&B)const{
        K = ::sgn(a.x, b.x) ? (b.y-a.y)/(b.x-a.x) : OO;
        B = a.y - K*a.x;
    }
    void getEquation(DB&A,DB&B,DB&C)const{A=a.y-b.y,B=b.x-a.x,C=det(a, b);}

    Line&push(DB r){ // 正数右手螺旋向里
        Po v=d()._1().lt()*r;a+=v,b+=v; rTs;
    }
};

inline DB dot(cLine l1,cLine l2){return dot(l1.d(),l2.d());}
inline DB dot(cLine l,cPo p){return dot(l.a,l.b,p);}
inline DB dot(cPo p,cLine l){return dot(p,l.a,l.b);}
inline DB det(cLine l1,cLine l2){return det(l1.d(),l2.d());}
inline DB det(cLine l,cPo p){return det(l.a,l.b,p);}
inline DB det(cPo p,cLine l){return det(p,l.a,l.b);}
inline DB ang(cLine l0,cLine l1){return ang(l0.d(),l1.d());}
inline DB ang(cLine l,cPo p){return ang(l.a,l.b,p);}
inline DB ang(cPo p,cLine l){return ang(p,l.a,l.b);}

inline int Line::sgn(cLine l)const{return dett(Ts, l);}
inline Po Line::operator*(cLine l)const{return a+d()*det(a,l)/det(Ts,l);}
inline Po operator&(cPo p,cLine l){return l*Line(p,p+l.d().lt());}
inline Po operator%(cPo p,cLine l){return p&l*2-p;}
inline Line push(Line l, DB r){return l.push(r);}

struct Seg: public Line{
    Seg(cPo a=Po(),cPo b=Po()):Line(a,b){}
    Seg(DB x0,DB y0,DB x1,DB y1):Line(x0,y0,x1,y1){}
    Seg(cLine l):Line(l){}
    Seg(const Po &a,DB alpha):Line(a,alpha){}
    Seg(DB A,DB B,DB C):Line(A,B,C){}

    inline int sgn(cPo p)const;
    inline bool qrt(cSeg l)const;
    inline int sgn(cSeg l)const;
};

 // -1不相交 0相交（不规范） 1相交（规范）

inline int Seg::sgn(cPo p)const{return -dott(p,a,b);}

// quick_rejection_test
inline bool Seg::qrt(cSeg l)const{
    return min(a.x,b.x)<=max(l.a.x,l.b.x)&&min(l.a.x,l.b.x)<=max(a.x,b.x)&&
        min(a.y,b.y)<=max(l.a.y,l.b.y)&&min(l.a.y,l.b.y)<=max(a.y,b.y);
}

inline int Seg::sgn(cSeg l)const{
    if (!qrt(l)) return -1;

    /*return
        (dett(a,b,l.a)*dett(a,b,l.b)<=0 &&
        dett(l.a,l.b,a)*dett(l.a,l.b,b)<=0)?1:-1;*/

    int d1=dett(a,b,l.a),d2=dett(a,b,l.b),d3=dett(l.a,l.b,a),d4=dett(l.a,l.b,b);
    if ((d1^d2)==-2&&(d3^d4)==-2)return 1;
    return ((!d1&&dott(l.a-a,l.a-b)<=0)||(!d2&&dott(l.b-a,l.b-b)<=0)||
            (!d3&&dott(a-l.a,a-l.b)<=0)||(!d4&&dott(b-l.a,b-l.b)<=0))?0:-1;
}

//inline DB dist2(cLine l,cPo p){return sqr(fabs(dot(lt(l.d()), p-l.a)))/l.len2();}
inline DB dist2(cLine l,cPo p){return sqr(fabs(det(l.d(), p-l.a)))/l.len2();}

inline DB dist2(cLine l1,cLine l2){return dett(l1,l2)?0:dist2(l1,l2.a);}

inline DB dist2(cSeg l,cPo p){
    Po pa = p - l.a, pb = p - l.b;
    if (dott(l.d(), pa) <= 0) return pa.len2();
    if (dott(l.d(), pb) >= 0) return pb.len2();
    return dist2(Line(l), p);
}

inline DB dist2(cSeg s,cLine l){
    Po v1=s.a-l.a,v2=s.b-l.a;DB d1=det(l.d(),v1),d2=det(l.d(),v2);
    return sgn(d1)!=sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2)))/l.len2();
}
inline DB dist2(cSeg l1,cSeg l2){
    if (~l1.sgn(l2)) return 0;
    else return min(dist2(l2,l1.a), dist2(l2,l1.b), dist2(l1,l2.a), dist2(l1,l2.b));
}
template<class T1, class T2> inline DB dist2(const T1& a, const T2& b){
    return dist2(b, a);
}

} using namespace CG;//}
//}

/** I/O Accelerator Interface .. **/ //{
#define g (c=getchar())
#define d isdigit(g)
#define p x=x*10+c-'0'
#define n x=x*10+'0'-c
#define pp l/=10,p
#define nn l/=10,n
template<class T> inline T& RD(T &x){
    char c;while(!d);x=c-'0';while(d)p;
    return x;
}
template<class T> inline T& RDD(T &x){
    char c;while(g,c!='-'&&!isdigit(c));
    if (c=='-'){x='0'-g;while(d)n;}
    else{x=c-'0';while(d)p;}
    return x;
}
inline DB& RF(DB &x){
    //scanf("%lf", &x);
    char c;while(g,c!='-'&&c!='.'&&!isdigit(c));
    if(c=='-')if(g=='.'){x=0;DB l=1;while(d)nn;x*=l;}
        else{x='0'-c;while(d)n;if(c=='.'){DB l=1;while(d)nn;x*=l;}}
    else if(c=='.'){x=0;DB l=1;while(d)pp;x*=l;}
        else{x=c-'0';while(d)p;if(c=='.'){DB l=1;while(d)pp;x*=l;}}
    return x;
}
#undef nn
#undef pp
#undef n
#undef p
#undef d
#undef g
inline char* RS(char *s){
    //gets(s);
    scanf("%s", s);
    return s;
}

LL last_ans; int Case; template<class T> inline void OT(const T &x){
    //printf("Case %d: ", ++Case);
    //printf("%lld\n", x);
    //printf("%.4f\n", x);
    printf("%d\n", x);
    //cout << x << endl;
    //last_ans = x;
}
//}

//}/* .................................................................................................................................. */

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

/** Micro Mezz Macro Flation -- Overheated Economy ., Last Update: Aug. 20th 2013 **/ //{

/** Header .. **/ //{

#pragma comment(linker, "/STACK:36777216")

//#pragma GCC optimize ("O2")

#define LOCAL

//#include "testlib.h"

#include <functional>

#include <algorithm>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <numeric>

#include <cstring>

#include <climits>

#include <cassert>

#include <complex>

#include <cstdio>

#include <string>

#include <vector>

#include <bitset>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <list>

#include <set>

#include <map>

//#include <tr1/unordered_set>

//#include <tr1/unordered_map>

//#include <array>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)

#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)

#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)

#define REP_1(i, n) for (int i=1;i<=int(n);++i)

#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)

#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)

#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)

#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)

#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)

#define REP_N(i, n) for (i=0;i<int(n);++i)

#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)

#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)

#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)

#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)

#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)

#define REP_1_N(i, n) for (i=1;i<=int(n);++i)

#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)

#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)

#define REP_C_N(i, n) for (int n____=(i=0,int(n));i<n____;++i)

#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i<b____;++i)

#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i>=a____;--i)

#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i<=n____;++i)

#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i<=b____;++i)

#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i>=a____;--i)

#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define REP_S(i, str) for (char*i=str;*i;++i)

#define REP_L(i, hd, nxt) for (int i=hd;i;i=nxt[i])

#define REP_G(i, u) REP_L(i,hd[u],suc)

#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)

#define DO(n) for ( int ____n = n; ____n-->0; )

#define REP_2(i, j, n, m) REP(i, n) REP(j, m)

#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)

#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)

#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)

#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)

#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)

#define ALL(A) A.begin(), A.end()

#define LLA(A) A.rbegin(), A.rend()

#define CPY(A, B) memcpy(A, B, sizeof(A))

#define INS(A, P, B) A.insert(A.begin() + P, B)

#define ERS(A, P) A.erase(A.begin() + P)

#define BSC(A, x) (lower_bound(ALL(A), x) - A.begin())

#define CTN(T, x) (T.find(x) != T.end())

#define SZ(A) int((A).size())

#define PB push_back

#define MP(A, B) make_pair(A, B)

#define PTT pair<T, T>

#define Ts *this

#define rTs return Ts

#define fi first

#define se second

#define re real()

#define im imag()

#define Rush for(int ____T=RD(); ____T--;)

#define Display(A, n, m) { \

REP(i, n){ \

REP(j, m-1) cout << A[i][j] << " "; \

cout << A[i][m-1] << endl; \

} \

}

#define Display_1(A, n, m) { \

REP_1(i, n){ \

REP_1(j, m-1) cout << A[i][j] << " "; \

cout << A[i][m] << endl; \

} \

}

typedef long long LL;

//typedef long double DB;

typedef double DB;

typedef unsigned UINT;

typedef unsigned long long ULL;

typedef vector<int> VI;

typedef vector<char> VC;

typedef vector<string> VS;

typedef vector<LL> VL;

typedef vector<DB> VF;

typedef set<int> SI;

typedef set<string> SS;

typedef map<int, int> MII;

typedef map<string, int> MSI;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;

typedef vector<PII> VII;

typedef vector<VI> VVI;

typedef vector<VII> VVII;

template<class T> inline T& RD(T &);

template<class T> inline void OT(const T &);

//inline int RD(){int x; return RD(x);}

inline LL RD(){LL x; return RD(x);}

inline DB& RF(DB &);

inline DB RF(){DB x; return RF(x);}

inline char* RS(char *s);

inline char& RC(char &c);

inline char RC();

inline char& RC(char &c){scanf(" %c", &c); return c;}

inline char RC(){char c; return RC(c);}

//inline char& RC(char &c){c = getchar(); return c;}

//inline char RC(){return getchar();}

template<class T> inline T& RDD(T &);

inline LL RDD(){LL x; return RDD(x);}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}

template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}

template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}

template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}

template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}

template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}

template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}

template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}

template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}

template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}

template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}

template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}

inline char& RC(char &a, char &b){RC(a), RC(b); return a;}

inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}

inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}

inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}

inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}

inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}

inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}

inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}

inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}

inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}

inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}

inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}

inline void RS(char *s1, char *s2){RS(s1), RS(s2);}

inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}

template<class T0,class T1>inline void RDD(T0&a, T1&b){RDD(a),RDD(b);}

template<class T0,class T1,class T2>inline void RDD(T0&a, T1&b, T2&c){RDD(a),RDD(b),RDD(c);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}

template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void CLR(T &A){A.clear();}

template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}

template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}

template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}

template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}

template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}

template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}

template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}

template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}

template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}

template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}

template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}

template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}

template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){while (!Q.empty()) Q.pop();}

template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){while (!Q.empty()) Q.pop();}

template<class T> inline void CLR(stack<T> &S){while (!S.empty()) S.pop();}

template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}

template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}

template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}

template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}

template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}

template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}

template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline bool EPT(T &a){return a.empty();}

template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}

template<class T, class C> inline T& SRT(T &A, C B){sort(ALL(A), B); return A;}

template<class T> inline T& RVS(T &A){reverse(ALL(A)); return A;}

template<class T> inline T& UNQQ(T &A){A.resize(unique(ALL(A))-A.begin());return A;}

template<class T> inline T& UNQ(T &A){SRT(A);return UNQQ(A);}

//}

/** Constant List .. **/ //{

const int MOD = int(1e9) + 7;

//int MOD = 99990001;

const int INF = 0x3f3f3f3f;

const LL INFF = 0x3f3f3f3f3f3f3f3fLL;

const DB EPS = 1e-12;

const DB OO = 1e20;

const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 0, 1, 0};

const int dy[] = {0, 1, 0, -1};

//}

/** Add On .. **/ //{

// <<= '0. Nichi Joo ., //{

template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}

template<class T> inline void checkMax(T &a,const T b){if (a<b) a=b;}

template<class T> inline void checkMin(T &a, T &b, const T x){checkMin(a, x), checkMin(b, x);}

template<class T> inline void checkMax(T &a, T &b, const T x){checkMax(a, x), checkMax(b, x);}

template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}

template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}

template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}

template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}

template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}

template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}

template<class T> inline T sqr(T a){return a*a;}

template<class T> inline T cub(T a){return a*a*a;}

template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}

inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}

inline int sgn(DB x, DB y){return sgn(x - y);}

inline DB cos(DB a, DB b, DB c){return (sqr(a)+sqr(b)-sqr(c))/(2*a*b);}

inline DB cot(DB x){return 1./tan(x);};

inline DB sec(DB x){return 1./cos(x);};

inline DB csc(DB x){return 1./sin(x);};

//}

// <<= '1. Bitwise Operation ., //{

namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}

inline bool _1(LL x, int i){return bool(x&1LL<<i);}

inline LL _1(int i){return 1LL<<i;}

inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){

x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);

x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);

x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);

x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);

x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);

return x;

}

inline LL reverse_bits(LL x){

x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);

x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);

x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);

x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);

x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);

x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);

return x;

}

template<class T> inline bool odd(T x){return x&1;}

template<class T> inline bool even(T x){return !odd(x);}

template<class T> inline T low_bit(T x) {return x & -x;}

template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}

template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}

template<class T> inline int cover_idx(T x){int p = 0; while (_1(p) < x ) ++p; return p;}

inline int clz(int x){return __builtin_clz(x);}

inline int clz(LL x){return __builtin_clzll(x);}

inline int ctz(int x){return __builtin_ctz(x);}

inline int ctz(LL x){return __builtin_ctzll(x);}

inline int lg2(int x){return !x ? -1 : 31 - clz(x);}

inline int lg2(LL x){return !x ? -1 : 63 - clz(x);}

inline int low_idx(int x){return !x ? -1 : ctz(x);}

inline int low_idx(LL x){return !x ? -1 : ctz(x);}

inline int high_idx(int x){return lg2(x);}

inline int high_idx(LL x){return lg2(x);}

inline int parity(int x){return __builtin_parity(x);}

inline int parity(LL x){return __builtin_parityll(x);}

inline int count_bits(int x){return __builtin_popcount(x);}

inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}

// <<= '9. Comutational Geometry .,//{

namespace CG{

#define cPo const Po&

#define cLine const Line&

#define cSeg const Seg&

inline DB dist2(DB x,DB y){return sqr(x)+sqr(y);}

struct Po{

DB x,y;Po(DB x=0,DB y=0):x(x),y(y){}

void in(){RF(x,y);}void out(){printf("(%.2f,%.2f)",x,y);}

inline friend istream&operator>>(istream&i,Po&p){return i>>p.x>>p.y;}

inline friend ostream&operator<<(ostream&o,Po p){return o<<"("<<p.x<<", "<<p.y<< ")";}

Po operator-()const{return Po(-x,-y);}

Po&operator+=(cPo p){x+=p.x,y+=p.y;rTs;}Po&operator-=(cPo p){x-=p.x,y-=p.y;rTs;}

Po&operator*=(DB k){x*=k,y*=k;rTs;}Po&operator/=(DB k){x/=k,y/=k;rTs;}

Po&operator*=(cPo p){rTs=Ts*p;}Po&operator/=(cPo p){rTs=Ts/p;}

Po operator+(cPo p)const{return Po(x+p.x,y+p.y);}Po operator-(cPo p)const{return Po(x-p.x,y-p.y);}

Po operator*(DB k)const{return Po(x*k,y*k);}Po operator/(DB k)const{return Po(x/k,y/k);}

Po operator*(cPo p)const{return Po(x*p.x-y*p.y,y*p.x+x*p.y);}Po operator/(cPo p)const{return Po(x*p.x+y*p.y,y*p.x-x*p.y)/p.len2();}

bool operator==(cPo p)const{return!sgn(x,p.x)&&!sgn(y,p.y);};bool operator!=(cPo p)const{return sgn(x,p.x)||sgn(y,p.y);}

bool operator<(cPo p)const{return sgn(x,p.x)<0||!sgn(x,p.x)&&sgn(y,p.y)<0;}bool operator<=(cPo p)const{return sgn(x,p.x)<0||!sgn(x,p.x)&&sgn(y,p.y)<=0;}

bool operator>(cPo p)const{return!(Ts<=p);}bool operator >=(cPo p)const{return!(Ts<p);}

DB len2()const{return dist2(x,y);}DB len()const{return sqrt(len2());}DB arg()const{return atan2(y,x);}

Po&_1(){rTs/=len();}Po&conj(){y=-y;rTs;}Po&lt(){swap(x,y),x=-x;rTs;}Po&rt(){swap(x,y),y=-y;rTs;}

Po&rot(DB a,cPo o=Po()){Ts-=o;Ts*=Po(cos(a),sin(a));rTs+=o;}

};

inline DB dot(DB x1,DB y1,DB x2,DB y2){return x1*x2+y1*y2;}

inline DB dot(cPo a,cPo b){return dot(a.x,a.y,b.x,b.y);}

inline DB dot(cPo p0,cPo p1,cPo p2){return dot(p1-p0,p2-p0);}

inline DB det(DB x1,DB y1,DB x2,DB y2){return x1*y2-x2*y1;}

inline DB det(cPo a,cPo b){return det(a.x,a.y,b.x,b.y);}

inline DB det(cPo p0,cPo p1,cPo p2){return det(p1-p0,p2-p0);}

inline DB ang(cPo p0,cPo p1){return acos(dot(p0,p1)/p0.len()/p1.len());}

inline DB ang(cPo p0,cPo p1,cPo p2){return ang(p1-p0,p2-p0);}

inline DB ang(cPo p0,cPo p1,cPo p2,cPo p3){return ang(p1-p0,p3-p2);}

inline DB dist2(const Po &a, const Po &b){return dist2(a.x-b.x, a.y-b.y);}

template<class T1, class T2> inline int dett(const T1 &x, const T2 &y){return sgn(det(x, y));}

template<class T1, class T2, class T3> inline int dett(const T1 &x, const T2 &y, const T3 &z){return sgn(det(x, y, z));}

template<class T1, class T2, class T3, class T4> inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(det(x, y, z, w));}

template<class T1, class T2> inline int dott(const T1 &x, const T2 &y){return sgn(dot(x, y));}

template<class T1, class T2, class T3> inline int dott(const T1 &x, const T2 &y, const T3 &z){return sgn(dot(x, y, z));}

template<class T1, class T2, class T3, class T4> inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(dot(x, y, z, w));}

template<class T1, class T2> inline DB arg(const T1 &x, const T2 &y){DB a=ang(x,y);return~dett(x,y)?a:2*PI-a;}

template<class T1, class T2, class T3> inline DB arg(const T1 &x, const T2 &y, const T3 &z){DB a=ang(x,y,z);return~dett(x,y,z)?a:2*PI-a;}

template<class T1, class T2, class T3, class T4> inline DB arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w){DB a=ang(x,y,z,w);return~dett(x,y,z,w)?a:2*PI-a;}

template<class T1, class T2> inline DB dist(const T1 &x, const T2 &y){return sqrt(dist2(x, y));}

template<class T1, class T2, class T3> inline DB dist(const T1 &x, const T2 &y, const T3 &z){return sqrt(dist2(x, y, z));}

inline Po _1(Po p){return p._1();}inline Po conj(Po p){return p.conj();}

inline Po lt(Po p){return p.lt();}inline Po rt(Po p){return p.rt();}

inline Po rot(Po p,DB a,cPo o=Po()){return p.rot(a,o);}

inline Po operator *(DB k,cPo p){return p*k;}

inline Po operator /(DB k,cPo p){return conj(p)*k/p.len2();}

typedef vector<Po> VP;

struct Line{

Po a,b;Line(cPo a=Po(),cPo b=Po()):a(a),b(b){}

Line(DB x0,DB y0,DB x1,DB y1):a(Po(x0,y0)),b(Po(x1,y1)){}

Line(cLine l):a(l.a),b(l.b){}

//Ax+By+C=0

Line(DB A,DB B,DB C){

C=-C;if(!::sgn(A))a=Po(0,C/B),b=Po(1,C/B);

else if(!::sgn(B))a=Po(C/A,0),b=Po(C/A,1);

else a=Po(0,C/B),b=Po(1,(C-A)/B);

}

void in(){a.in(),b.in();}

inline friend istream&operator>>(istream&i,Line& p){return i>>p.a>>p.b;}

inline friend ostream&operator<<(ostream&o,Line p){return o<<p.a<<"-"<< p.b;}

Line operator+(cPo x)const{return Line(a+x,b+x);}

Line operator-(cPo x)const{return Line(a-x,b-x);}

Line operator*(DB k)const{return Line(a*k,b*k);}

Line operator/(DB k)const{return Line(a/k,b/k);}

Po operator*(cLine)const;

Po d()const{return b-a;}DB len2()const{return d().len2();}DB len()const{return d().len();}DB arg()const{return d().arg();}

int sgn(cPo p)const{return dett(a, b, p);}

int sgn(cLine)const;

bool sameSgn(cPo p1,cPo p2)const{return sgn(p1)==sgn(p2);}

void getEquation(DB&K,DB&B)const{

K = ::sgn(a.x, b.x) ? (b.y-a.y)/(b.x-a.x) : OO;

B = a.y - K*a.x;

}

void getEquation(DB&A,DB&B,DB&C)const{A=a.y-b.y,B=b.x-a.x,C=det(a, b);}

Line&push(DB r){ // 正数右手螺旋向里

Po v=d()._1().lt()*r;a+=v,b+=v; rTs;

}

};

inline DB dot(cLine l1,cLine l2){return dot(l1.d(),l2.d());}

inline DB dot(cLine l,cPo p){return dot(l.a,l.b,p);}

inline DB dot(cPo p,cLine l){return dot(p,l.a,l.b);}

inline DB det(cLine l1,cLine l2){return det(l1.d(),l2.d());}

inline DB det(cLine l,cPo p){return det(l.a,l.b,p);}

inline DB det(cPo p,cLine l){return det(p,l.a,l.b);}

inline DB ang(cLine l0,cLine l1){return ang(l0.d(),l1.d());}

inline DB ang(cLine l,cPo p){return ang(l.a,l.b,p);}

inline DB ang(cPo p,cLine l){return ang(p,l.a,l.b);}

inline int Line::sgn(cLine l)const{return dett(Ts, l);}

inline Po Line::operator*(cLine l)const{return a+d()*det(a,l)/det(Ts,l);}

inline Po operator&(cPo p,cLine l){return l*Line(p,p+l.d().lt());}

inline Po operator%(cPo p,cLine l){return p&l*2-p;}

inline Line push(Line l, DB r){return l.push(r);}

struct Seg: public Line{

Seg(cPo a=Po(),cPo b=Po()):Line(a,b){}

Seg(DB x0,DB y0,DB x1,DB y1):Line(x0,y0,x1,y1){}

Seg(cLine l):Line(l){}

Seg(const Po &a,DB alpha):Line(a,alpha){}

Seg(DB A,DB B,DB C):Line(A,B,C){}

inline int sgn(cPo p)const;

inline bool qrt(cSeg l)const;

inline int sgn(cSeg l)const;

};

// -1不相交 0相交（不规范） 1相交（规范）

inline int Seg::sgn(cPo p)const{return -dott(p,a,b);}

// quick_rejection_test

inline bool Seg::qrt(cSeg l)const{

return min(a.x,b.x)<=max(l.a.x,l.b.x)&&min(l.a.x,l.b.x)<=max(a.x,b.x)&&

min(a.y,b.y)<=max(l.a.y,l.b.y)&&min(l.a.y,l.b.y)<=max(a.y,b.y);

}

inline int Seg::sgn(cSeg l)const{

if (!qrt(l)) return -1;

/*return

(dett(a,b,l.a)*dett(a,b,l.b)<=0 &&

dett(l.a,l.b,a)*dett(l.a,l.b,b)<=0)?1:-1;*/

int d1=dett(a,b,l.a),d2=dett(a,b,l.b),d3=dett(l.a,l.b,a),d4=dett(l.a,l.b,b);

if ((d1^d2)==-2&&(d3^d4)==-2)return 1;

return ((!d1&&dott(l.a-a,l.a-b)<=0)||(!d2&&dott(l.b-a,l.b-b)<=0)||

(!d3&&dott(a-l.a,a-l.b)<=0)||(!d4&&dott(b-l.a,b-l.b)<=0))?0:-1;

}

//inline DB dist2(cLine l,cPo p){return sqr(fabs(dot(lt(l.d()), p-l.a)))/l.len2();}

inline DB dist2(cLine l,cPo p){return sqr(fabs(det(l.d(), p-l.a)))/l.len2();}

inline DB dist2(cLine l1,cLine l2){return dett(l1,l2)?0:dist2(l1,l2.a);}

inline DB dist2(cSeg l,cPo p){

Po pa = p - l.a, pb = p - l.b;

if (dott(l.d(), pa) <= 0) return pa.len2();

if (dott(l.d(), pb) >= 0) return pb.len2();

return dist2(Line(l), p);

}

inline DB dist2(cSeg s,cLine l){

Po v1=s.a-l.a,v2=s.b-l.a;DB d1=det(l.d(),v1),d2=det(l.d(),v2);

return sgn(d1)!=sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2)))/l.len2();

}

inline DB dist2(cSeg l1,cSeg l2){

if (~l1.sgn(l2)) return 0;

else return min(dist2(l2,l1.a), dist2(l2,l1.b), dist2(l1,l2.a), dist2(l1,l2.b));

}

template<class T1, class T2> inline DB dist2(const T1& a, const T2& b){

return dist2(b, a);

}

} using namespace CG;//}

//}

/** I/O Accelerator Interface .. **/ //{

#define g (c=getchar())

#define d isdigit(g)

#define p x=x*10+c-'0'

#define n x=x*10+'0'-c

#define pp l/=10,p

#define nn l/=10,n

template<class T> inline T& RD(T &x){

char c;while(!d);x=c-'0';while(d)p;

return x;

}

template<class T> inline T& RDD(T &x){

char c;while(g,c!='-'&&!isdigit(c));

if (c=='-'){x='0'-g;while(d)n;}

else{x=c-'0';while(d)p;}

return x;

}

inline DB& RF(DB &x){

//scanf("%lf", &x);

char c;while(g,c!='-'&&c!='.'&&!isdigit(c));

if(c=='-')if(g=='.'){x=0;DB l=1;while(d)nn;x*=l;}

else{x='0'-c;while(d)n;if(c=='.'){DB l=1;while(d)nn;x*=l;}}

else if(c=='.'){x=0;DB l=1;while(d)pp;x*=l;}

else{x=c-'0';while(d)p;if(c=='.'){DB l=1;while(d)pp;x*=l;}}

return x;

}

#undef nn

#undef pp

#undef n

#undef p

#undef d

#undef g

inline char* RS(char *s){

//gets(s);

scanf("%s", s);

return s;

}

LL last_ans; int Case; template<class T> inline void OT(const T &x){

//printf("Case %d: ", ++Case);

//printf("%lld\n", x);

//printf("%.4f\n", x);

printf("%d\n", x);

//cout << x << endl;

//last_ans = x;

}

//}

//}/* .................................................................................................................................. */

[Dr.Lib]Note:Algorithms – GarsiaWachs

Via FHQ神犇http://fanhq666.blog.163.com/blog/static/81943426201062865551410/

石子合并（每次合并相邻的两堆石子，代价为这两堆石子的重量和，把一排石子合并为一堆，求最小代价）是一个经典的问题。dp可以做到O(n*n)的时间复杂度，方法是：

朴素DP做法

设f[i,j]为合并从i到j的石子所用最小代价。

f[i,j]=min(sum(i,j)+f[i,k]+f[k+1,j])对所有i<=k<j，其中sum(i,j)表示从i到j的石子重量之和。

设上式取等时k的值为w[i,j]，有神牛证明过：w[i,j]>=w[i,j-1],w[i,j]<=w[i+1,j]

这样，枚举k的时候，就有了一个上下界，从而搞掉了一维。

GarsiaWachs算法

而GarsiaWachs算法可以把时间复杂度压缩到O(nlogn)。

具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W,Lemma X,Lemma Y,Lemma Z。

只能说一个概要吧：

设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，（方便起见设A[-1]和A[n]等于正无穷大）
那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。

有定理保证，如此操作后问题的答案不会改变。

举个例子：

186 64 35 32 103

因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面

186 64（k=3,A[3]与A[2]都被删除了） 103

186 67（遇到了从右向左第一个比67大的数，我们把67插入到他后面） 64 103

186 67 64 103 （有定理保证这个序列的答案加上67就等于原序列的答案）

现在由5个数变为4个数了，继续！

186 （k=2,67和64被删除了）103

186 131（就插入在这里） 103

186 131 103

现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）

234 186

420

最后的答案呢？就是各次合并的重量之和呗。420+234+131+67=852，哈哈，算对了。

证明嘛，基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变。详见TAOCP。

实现

具体实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”

朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化（好熟悉的优化方法），使得最终复杂度为O(nlogn)

#include <cstdio>
#define NMax 50000
using namespace std;
int A[NMax],N,T;
int ret;
void combine(int k){
	int tmp=A[k]+A[k-1],j;
	ret+=tmp;
	for (int i=k;i<T-1;i++)A[i]=A[i+1];
	T--;
	for (j=k-1;j>0 && A[j-1]<tmp;j--)A[j]=A[j-1];
	A[j]=tmp;
	while (j>=2 && A[j]>=A[j-2]){
		int d=T-j;
		combine(j-1);
		j=T-d;
	}
}
int main()
{
	while (scanf("%d",&N),N){
		for (int i=0;i<N;i++)scanf("%d",A+i);
		T=1;ret=0;
		for (int i=1;i<N;i++){
			A[T++]=A[i];
			while (T>=3 && A[T-3]<=A[T-1])combine(T-2);
		}
		while (T>1)combine(T-1);
		printf("%d\n",ret);
	}
	return 0;
}

#include <cstdio>

#define NMax 50000

using namespace std;

int A[NMax],N,T;

int ret;

void combine(int k){

int tmp=A[k]+A[k-1],j;

ret+=tmp;

for (int i=k;i<T-1;i++)A[i]=A[i+1];

T--;

for (j=k-1;j>0 && A[j-1]<tmp;j--)A[j]=A[j-1];

A[j]=tmp;

while (j>=2 && A[j]>=A[j-2]){

int d=T-j;

combine(j-1);

j=T-d;

}

int main()

{

while (scanf("%d",&N),N){

for (int i=0;i<N;i++)scanf("%d",A+i);

T=1;ret=0;

for (int i=1;i<N;i++){

A[T++]=A[i];

while (T>=3 && A[T-3]<=A[T-1])combine(T-2);

}

while (T>1)combine(T-1);

printf("%d\n",ret);

}

return 0;

}

[Dr.Lib]Note:Algorithms – Segment Tree 线段树

Via http://en.wikipedia.org/wiki/Segment_tree

In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

Applications of the segment tree are in the areas of computational geometry, and geographic information systems.

The segment tree can be generalized to higher dimension spaces as well.

Graphic example of the structure of the segment tree. This instance is built for the segments shown at the bottom.

继续阅读→

Category Archives: Algorithm

[Dr.Lib]Note:Algorithms – LLRB——红黑树的现代实现

一、本文内容

二、算法应用

三、2-3-4树

四、红黑树

1、定义

2、插入算法

3、删除算法

[Dr.Lib]Note:Algorithms – 四边形不等式

2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n)

1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1)

[Dr.Lib]Note:Coding – 日常模板 Manual Ver-0.1

[Dr.Lib]Note:Algorithms – GarsiaWachs

朴素DP做法

GarsiaWachs算法

实现

[Dr.Lib]Note:Algorithms – Segment Tree 线段树

朋友们

TAG CLOUD