using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Problem : IDisposable
{
private Scanner sc;
private Printer pr;
public Problem(Scanner scanner, Printer printer)
{
sc = scanner;
pr = printer;
Initiate();
}
public Problem() : this(new Scanner(), new Printer()) { }
public Problem(Scanner scanner) : this(scanner, new Printer()) { }
public Problem(Printer printer) : this(new Scanner(), printer) { }
public void Dispose()
{
sc.Dispose();
pr.Dispose();
}
private int A;
private int B;
private int C;
private int D;
private void Initiate()
{
sc.Read(out A, out B, out C, out D);
}
public void Solve()
{
var d = A * D - B * C;
pr.WriteLine(d < 0 ? "TAKAHASHI" : d > 0 ? "AOKI" : "DRAW");
}
}
class Program
{
static void Main()
{
using (var problem = new Problem()) problem.Solve();
}
}
class UndirectedGraph<V, E> : DirectedGraph<V, E>
{
public UndirectedGraph(int V) : base(V) { }
public UndirectedGraph(int V, IEnumerable<EdgeInfo<E>> edges) : base(V, edges) { }
public override void AddEdge(EdgeInfo<E> edge)
{
edges.Add(edge);
edgeFrom[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
edgeFrom[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
edgeTo[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
edgeTo[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
}
public bool IsConnected
{
get
{
if (numberOfNodes == 0) return true;
var used = new bool[numberOfNodes];
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0)
{
var v = queue.Dequeue();
if (used[v]) continue;
used[v] = true;
foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
}
return used.All(x => x);
}
}
public bool IsTree
{
get
{
if (numberOfNodes == 0) return true;
var used = new bool[numberOfNodes];
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0)
{
var v = queue.Dequeue();
if (used[v]) return false;
used[v] = true;
foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
}
return used.All(x => x);
}
}
public UndirectedGraph<V, E> MinimumSpanningTreePrim(int start, Func<E, int> cost)
{
var graph = new UndirectedGraph<V, E>(numberOfNodes);
nodes.CopyTo(graph.nodes, 0);
var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
var used = new bool[numberOfNodes];
var queue = new PriorityQueue<Pair<EdgeInfo<E>, int>>((x, y) => x.Second.CompareTo(y.Second), numberOfNodes);
d[start] = 0;
queue.Enqueue(new Pair<EdgeInfo<E>, int>(new EdgeInfo<E>(-1, 0, default(E)), 0));
while (queue.Count > 0)
{
var p = queue.Dequeue();
var v = p.First.To;
if (d[v] < p.Second) continue;
used[v] = true;
if (p.First.From >= 0) graph.AddEdge(v, p.First.From, p.First.Information);
foreach (var w in EdgesFrom(v))
{
if (!used[w.End] && cost(w.Information) < d[w.End])
{
d[w.End] = cost(w.Information);
queue.Enqueue(new Pair<EdgeInfo<E>, int>(new EdgeInfo<E>(v, w.End, w.Information), cost(w.Information)));
}
}
}
return graph;
}
public UndirectedGraph<V, E> MinimumSpanningTreeKruskal(Func<E, int> cost)
{
var graph = new UndirectedGraph<V, E>(numberOfNodes);
nodes.CopyTo(graph.nodes, 0);
var tree = new UnionFindTree(numberOfNodes);
edges.Sort((x, y) => cost(x.Information).CompareTo(cost(y.Information)));
foreach (var e in edges)
{
if (!tree.IsSameCategory(e.From, e.To))
{
tree.UniteCategory(e.From, e.To);
graph.AddEdge(e);
}
}
return graph;
}
public bool IsBipartite
{
get
{
var color = new int[numberOfNodes];
foreach (var v in nodes)
{
if (color[v.Code] == 0)
{
var queue = new Queue<Pair<int, int>>();
queue.Enqueue(new Pair<int, int>(v.Code, 1));
while (queue.Count > 0)
{
var w = queue.Dequeue();
if (color[w.First] != 0)
{
if (color[w.First] != w.Second)
return false;
continue;
}
color[w.First] = w.Second;
foreach (var e in EdgesFrom(w.First)) queue.Enqueue(new Pair<int, int>(e.End, -w.Second));
}
}
}
return true;
}
}
public string ToString(Func<NodeInfo<V>, string> vertex, Func<EdgeInfo<E>, string> edge)
{
var sb = new StringBuilder();
sb.Append("graph G {\n");
foreach (var v in nodes) sb.Append("\tv" + v.Code + " [label = \"" + vertex(v) + "\"];\n");
foreach (var e in edges) sb.Append("\tv" + e.From + " -- v" + e.To + " [label=\"" + edge(e) + "\"];\n");
sb.Append("}");
return sb.ToString();
}
public override string ToString() { return ToString(v => v.ToString(), e => e.ToString()); }
}
class NodeInfo<V> : Pair<int, V>
{
public int Code { get { return First; } set { First = value; } }
public V Information { get { return Second; } set { Second = value; } }
public NodeInfo() : base() { }
public NodeInfo(int code, V info) : base(code, info) { }
}
class HalfEdgeInfo<E> : Pair<int, E>
{
public int End { get { return First; } set { First = value; } }
public E Information { get { return Second; } set { Second = value; } }
public HalfEdgeInfo() : base() { }
public HalfEdgeInfo(int end, E info) : base(end, info) { }
}
class EdgeInfo<E> : Pair<Pair<int, int>, E>
{
public int From { get { return First.First; } set { First.First = value; } }
public int To { get { return First.Second; } set { First.Second = value; } }
public E Information { get { return Second; } set { Second = value; } }
public EdgeInfo() : base() { }
public EdgeInfo(int from, int to, E info) : base(new Pair<int, int>(from, to), info) { }
}
class DirectedGraph<V, E> : IEnumerable<NodeInfo<V>>
{
protected int numberOfNodes;
protected NodeInfo<V>[] nodes;
protected List<EdgeInfo<E>> edges;
protected List<HalfEdgeInfo<E>>[] edgeFrom;
protected List<HalfEdgeInfo<E>>[] edgeTo;
public IEnumerable<HalfEdgeInfo<E>> EdgesFrom(int node) { return edgeFrom[node]; }
public int InDegree(int node) { return edgeTo[node].Count; }
public int OutDegree(int node) { return edgeFrom[node].Count; }
public IEnumerable<HalfEdgeInfo<E>> EdgesTo(int node) { return edgeTo[node]; }
public V this[int node] { get { return nodes[node].Second; } set { nodes[node].Second = value; } }
public IEnumerable<EdgeInfo<E>> Edges { get { return edges; } }
public DirectedGraph(int V)
{
numberOfNodes = V;
nodes = Enumerable.Range(0, V).Select(x => new NodeInfo<V>(x, default(V))).ToArray();
edges = new List<EdgeInfo<E>>();
edgeFrom = Enumerable.Range(0, V).Select(_ => new List<HalfEdgeInfo<E>>()).ToArray();
edgeTo = Enumerable.Range(0, V).Select(_ => new List<HalfEdgeInfo<E>>()).ToArray();
}
public DirectedGraph(int V, IEnumerable<EdgeInfo<E>> edges) : this(V) { foreach (var e in edges) AddEdge(e.From, e.To, e.Information); }
public virtual void AddEdge(EdgeInfo<E> edge)
{
edges.Add(edge);
edgeFrom[edge.From].Add(new HalfEdgeInfo<E>(edge.To, edge.Information));
edgeTo[edge.To].Add(new HalfEdgeInfo<E>(edge.From, edge.Information));
}
public void AddEdge(int from, int to, E information) { AddEdge(new EdgeInfo<E>(from, to, information)); }
public void AddEdge(V from, V to, E information) { AddEdge(new EdgeInfo<E>(SearchNode(from).Code, SearchNode(to).Code, information)); }
public NodeInfo<V> SearchNode(V node) { return nodes.FirstOrDefault(e => e.Information.Equals(node)); }
public EdgeInfo<E> SearchEdge(E edge) { return edges.Find(e => e.Information.Equals(edge)); }
public IEnumerator<NodeInfo<V>> GetEnumerator() { foreach (var v in nodes) yield return v; }
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
public int[] ShortestPathLengthFrom(int from, Func<E, int> cost)
{
var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
d[from] = 0;
var update = true;
while (update)
{
update = false;
foreach (var e in edges)
{
var tmp = d[e.From] + cost(e.Information);
if (d[e.From] < Func.Inf && d[e.To] > tmp)
{
d[e.To] = tmp;
update = true;
}
}
}
return d;
}
// cost(e)>=0
public int[] DijkstraFrom(int from, Func<E, int> cost)
{
var d = Enumerable.Repeat(Func.Inf, numberOfNodes).ToArray();
var queue = new PriorityQueue<Pair<int, int>>((x, y) => x.Second.CompareTo(y.Second));
d[from] = 0;
queue.Enqueue(new Pair<int, int>(from, 0));
while (!queue.IsEmpty)
{
var p = queue.Dequeue();
var v = p.First;
if (d[v] < p.Second) continue;
foreach (var e in EdgesFrom(v))
{
var tmp = d[v] + cost(e.Information);
if (d[e.End] > tmp)
{
d[e.End] = tmp;
queue.Enqueue(new Pair<int, int>(e.End, d[e.End]));
}
}
}
return d;
}
public int[,] ShortestPathLengthEachOther(Func<E, int> cost)
{
var d = new int[numberOfNodes, numberOfNodes];
for (var v = 0; v < numberOfNodes; v++) for (var w = 0; w < numberOfNodes; w++) d[v, w] = Func.Inf;
for (var v = 0; v < numberOfNodes; v++) d[v, v] = 0;
foreach (var e in edges) if (e.From != e.To) d[e.From, e.To] = cost(e.Information);
for (var k = 0; k < numberOfNodes; k++)
for (var v = 0; v < numberOfNodes; v++)
for (var w = 0; w < numberOfNodes; w++)
d[v, w] = Math.Min(d[v, w], d[v, k] + d[k, w]);
return d;
}
public bool ContainsNegativeLoopWF(Func<E, int> cost)
{
var d = ShortestPathLengthEachOther(cost);
for (var v = 0; v < numberOfNodes; v++) if (d[v, v] < 0) return true;
return false;
}
public bool ContainsNegativeLoop(Func<E, int> cost)
{
var d = Enumerable.Repeat(0, numberOfNodes).ToArray();
for (var v = 0; v < numberOfNodes; v++)
{
foreach (var e in edges)
{
var tmp = d[e.From] + cost(e.Information);
if (d[e.To] > tmp)
{
d[e.To] = tmp;
if (v == numberOfNodes - 1) return true;
}
}
}
return false;
}
public IEnumerable<int> ReachableFrom(int from)
{
var used = new bool[numberOfNodes];
var queue = new Queue<int>();
queue.Enqueue(from);
while (queue.Count > 0)
{
var v = queue.Dequeue();
if (used[v]) continue;
used[v] = true;
foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
}
for (var v = 0; v < numberOfNodes; v++) if (used[v]) yield return v;
}
public bool IsReachable(int from, int to)
{
var used = new bool[numberOfNodes];
var queue = new Queue<int>();
queue.Enqueue(from);
while (queue.Count > 0)
{
var v = queue.Dequeue();
if (v == to) return true;
if (used[v]) continue;
used[v] = true;
foreach (var e in EdgesFrom(v)) queue.Enqueue(e.End);
}
return false;
}
public string ToString(Func<V, string> vertex, Func<E, string> edge)
{
var sb = new StringBuilder();
sb.Append("digraph G {\n");
foreach (var v in nodes) sb.Append("\tv" + v.Code + " [label = \"" + vertex(v.Information) + "\"];\n");
foreach (var e in edges) sb.Append("\tv" + e.From + " -> v" + e.To + " [label=\"" + edge(e.Information) + "\"];\n");
sb.Append("}");
return sb.ToString();
}
public override string ToString() { return ToString(v => v.ToString(), e => e.ToString()); }
}
class UnionFindTree
{
private int N;
private List<int> parent;
private List<int> rank;
public UnionFindTree(int capacity)
{
parent = new List<int>(capacity);
rank = new List<int>(capacity);
N = capacity;
for (var i = 0; i < capacity; i++)
{
parent.Add(i);
rank.Add(0);
}
}
public void Add(int x)
{
if (x >= N)
{
for (var i = N; i <= x; i++)
{
parent.Add(i);
parent.Add(0);
}
N = x + 1;
}
}
private int GetRootOf(int x)
{
Add(x);
if (parent[x] == x) return x;
else return parent[x] = GetRootOf(parent[x]);
}
public void UniteCategory(int x, int y)
{
x = GetRootOf(x);
y = GetRootOf(y);
if (x == y) return;
if (rank[x] < rank[y]) parent[x] = y;
else
{
parent[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}
public bool IsSameCategory(int x, int y) { return GetRootOf(x) == GetRootOf(y); }
}
class AVLTree<T> : IEnumerable<T>, ICollection<T>, ICollection, IEnumerable
{
private class AVLNode : IEnumerable<T>
{
private AVLTree<T> tree;
private int height;
public int Height { get { return height; } }
public int Bias { get { return Left.height - Right.height; } }
public T Item;
public AVLNode Parent;
public AVLNode Left;
public AVLNode Right;
private AVLNode(T x, AVLTree<T> tree) { this.tree = tree; Item = x; Left = tree.sentinel; Right = tree.sentinel; }
public AVLNode(AVLTree<T> tree) : this(default(T), tree) { height = 0; Parent = null; }
public AVLNode(T x, AVLNode parent, AVLTree<T> tree) : this(x, tree) { this.height = 1; this.Parent = parent; }
public void Adjust() { height = 1 + Math.Max(Left.height, Right.height); }
public void ResetAsSentinel() { height = 0; Left = tree.sentinel; Right = tree.sentinel; }
public IEnumerator<T> GetEnumerator()
{
if (this != tree.sentinel)
{
foreach (var x in Left) yield return x;
yield return Item;
foreach (var x in Right) yield return x;
}
}
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
}
private AVLNode sentinel;
private Comparison<T> comp;
private Func<T, T, bool> equals;
private int count;
// assumed to be comparer
// i.e. comp(x,x)=0, and comp(x,y)>0 then comp(y,x)<0, and comp(x,y)>0 & comp(y,z)>0 then comp(x,z)>0
public AVLTree(Comparison<T> comp)
{
sentinel = new AVLNode(this);
sentinel.ResetAsSentinel();
this.comp = comp;
if (typeof(T).IsValueType) equals = (x, y) => x.Equals(y);
else equals = (x, y) => ReferenceEquals(x, y);
count = 0;
}
public AVLTree(IComparer<T> comp) : this((x, y) => comp.Compare(x, y)) { }
private void Replace(AVLNode u, AVLNode v)
{
var parent = u.Parent;
if (parent.Left == u) parent.Left = v;
else parent.Right = v;
v.Parent = parent;
}
private AVLNode RotateL(AVLNode v)
{
var u = v.Right;
Replace(v, u);
v.Right = u.Left;
u.Left.Parent = v;
u.Left = v;
v.Parent = u;
v.Adjust();
u.Adjust();
return u;
}
private AVLNode RotateR(AVLNode u)
{
var v = u.Left;
Replace(u, v);
u.Left = v.Right;
v.Right.Parent = u;
v.Right = u;
u.Parent = v;
u.Adjust();
v.Adjust();
return v;
}
private AVLNode RotateLR(AVLNode t) { RotateL(t.Left); return RotateR(t); }
private AVLNode RotateRL(AVLNode t) { RotateR(t.Right); return RotateL(t); }
private void Adjust(bool isInsertMode, AVLNode node)
{
while (node.Parent != sentinel)
{
var parent = node.Parent;
var height = parent.Height;
if ((parent.Left == node) == isInsertMode)
if (parent.Bias == 2)
if (parent.Left.Bias >= 0)
parent = RotateR(parent);
else
parent = RotateLR(parent);
else parent.Adjust();
else
if (parent.Bias == -2)
if (parent.Right.Bias <= 0)
parent = RotateL(parent);
else
parent = RotateRL(parent);
else parent.Adjust();
if (height == parent.Height) break;
node = parent;
}
}
public void Add(T item)
{
var parent = sentinel;
var pos = sentinel.Left;
var isLeft = true;
count++;
while (pos != sentinel)
if (comp(item, pos.Item) < 0) { parent = pos; pos = pos.Left; isLeft = true; }
else { parent = pos; pos = pos.Right; isLeft = false; }
if (isLeft)
{
parent.Left = new AVLNode(item, parent, this);
Adjust(true, parent.Left);
}
else
{
parent.Right = new AVLNode(item, parent, this);
Adjust(true, parent.Right);
}
}
// if equals(x,y) holds then !(comp(x,y)<0) and !(comp(x,y)>0) must hold
// i.e. equals(x,y) -> comp(x,y)=0
private bool Remove(T item, AVLNode start)
{
var pos = start;
while (pos != sentinel)
{
if (comp(item, pos.Item) < 0) pos = pos.Left;
else if (comp(item, pos.Item) > 0) pos = pos.Right;
else if (equals(pos.Item, item))
{
if (pos.Left == sentinel)
{
Replace(pos, pos.Right);
Adjust(false, pos.Right);
}
else
{
var max = Max(pos.Left);
pos.Item = max.Item;
Replace(max, max.Left);
Adjust(false, max.Left);
}
count--;
return true;
}
else return Remove(item, pos.Left) || Remove(item, pos.Right);
}
return false;
}
public bool Remove(T item) { return Remove(item, sentinel.Left); }
private AVLNode Max(AVLNode node)
{
while (node.Right != sentinel) node = node.Right;
return node;
}
private AVLNode Min(AVLNode node)
{
while (node.Left != sentinel) node = node.Left;
return node;
}
public bool Contains(T item)
{
var pos = sentinel.Left;
while (pos != sentinel)
{
if (comp(item, pos.Item) < 0) pos = pos.Left;
else if (comp(item, pos.Item) > 0) pos = pos.Right;
else return true;
}
return false;
}
public T Find(T item)
{
var pos = sentinel.Left;
while (pos != sentinel)
{
if (comp(item, pos.Item) < 0) pos = pos.Left;
else if (comp(item, pos.Item) > 0) pos = pos.Right;
else return pos.Item;
}
return default(T);
}
public T Min() { return Min(sentinel.Left).Item; }
public T Max() { return Max(sentinel.Left).Item; }
public bool IsEmpty { get { return sentinel.Left == sentinel; } }
public void Clear() { sentinel.Left = sentinel; count = 0; sentinel.ResetAsSentinel(); }
public IEnumerator<T> GetEnumerator() { return sentinel.Left.GetEnumerator(); }
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
public void CopyTo(T[] array, int arrayIndex) { foreach (var x in this) array[arrayIndex++] = x; }
public int Count { get { return count; } }
public bool IsReadOnly { get { return true; } }
public void CopyTo(Array array, int index) { foreach (var x in this) array.SetValue(x, index++); }
public bool IsSynchronized { get { return false; } }
public object SyncRoot { get { return null; } }
public override string ToString()
{
var nodes = new StringBuilder();
var edges = new StringBuilder();
ConcatSubTree(nodes, edges, sentinel.Left, "L");
return "digraph G {\n" + nodes.ToString() + edges.ToString() + "}";
}
private void ConcatSubTree(StringBuilder nodes, StringBuilder edges, AVLNode node, string code)
{
if (node == sentinel) return;
nodes.Append("\tv" + code + " [label = \"" + node.Height + ":" + node.Item + "\"];\n");
if (node.Left != sentinel) edges.Append("\tv" + code + " -> v" + code + "L;\n");
if (node.Right != sentinel) edges.Append("\tv" + code + " -> v" + code + "R;\n");
ConcatSubTree(nodes, edges, node.Left, code + "L");
ConcatSubTree(nodes, edges, node.Right, code + "R");
}
public bool IsBalanced() { return IsBalanced(sentinel.Left); }
public bool IsValidBinarySearchTree() { return IsValidBinarySearchTree(sentinel.Left); }
private bool IsBalanced(AVLNode node) { return node == sentinel || (Math.Abs(node.Bias) < 2 && IsBalanced(node.Left) && IsBalanced(node.Right)); }
private bool IsValidBinarySearchTree(AVLNode node)
{
return node == sentinel || (Small(node.Item, node.Left) && Large(node.Item, node.Right)
&& IsValidBinarySearchTree(node.Left) && IsValidBinarySearchTree(node.Right));
}
private bool Small(T item, AVLNode node) { return node == sentinel || (comp(item, node.Item) >= 0 && Small(item, node.Left) && Small(item, node.Right)); }
private bool Large(T item, AVLNode node) { return node == sentinel || (comp(item, node.Item) <= 0 && Large(item, node.Left) && Large(item, node.Right)); }
public static void CheckAVL(Random rand, int N)
{
Comparison<double> comp = (x, y) => x.CompareTo(y);
var avl = new AVLTree<double>(comp);
var toBeLeft = new double[N];
var toBeRemoved = new double[N];
for (var i = 0; i < N; i++) avl.Add(toBeRemoved[i] = rand.NextDouble());
for (var i = 0; i < N; i++) avl.Add(toBeLeft[i] = rand.NextDouble());
for (var i = 0; i < N; i++) Console.Write(avl.Remove(toBeRemoved[i]) ? "" : "!!!NOT REMOVED!!! => " + toBeRemoved[i] + "\n");
var insertErrors = toBeLeft.All(x => avl.Contains(x));
var deleteErrors = avl.Count == N;
//Console.WriteLine("【AVL木の構造】");
//Console.WriteLine(avl);
if (insertErrors && deleteErrors) Console.WriteLine("○\t挿入, 削除操作が正しく行われています.");
else if (insertErrors) Console.WriteLine("×\t挿入(または削除)操作に問題があります.");
else Console.WriteLine("×\t削除(または挿入)操作に問題があります.");
if (avl.IsBalanced()) Console.WriteLine("○\tAVL木は平衡条件を保っています.");
else Console.WriteLine("×\tAVL木の平衡条件が破れています.");
if (avl.IsValidBinarySearchTree()) Console.WriteLine("○\tAVL木は二分探索木になっています.");
else Console.WriteLine("×\tAVL木は二分探索木になっていません.");
Array.Sort(toBeLeft, comp);
Console.WriteLine("最小値 : " + avl.Min() + " ≡ " + toBeLeft.First());
Console.WriteLine("最大値 : " + avl.Max() + " ≡ " + toBeLeft.Last());
Console.WriteLine("要素数 : " + avl.Count + "個");
}
}
class PriorityQueue<T> : IEnumerable<T>, ICollection, IEnumerable
{
private Comparison<T> comp;
private List<T> list;
private int count;
public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }
public PriorityQueue(Comparison<T> comparison)
{
comp = comparison;
list = new List<T>();
count = 0;
}
public PriorityQueue(Comparison<T> comparison, IEnumerable<T> source) : this(comparison) { foreach (var x in source) Enqueue(x); }
public PriorityQueue(Comparison<T> comparison, int capacity) : this(comparison) { list.Capacity = capacity; }
/// <summary>
/// add an item
/// this is an O(log n) operation
/// </summary>
/// <param name="x">item</param>
public void Enqueue(T x)
{
var pos = count++;
list.Add(x);
while (pos > 0)
{
var p = (pos - 1) / 2;
if (comp(list[p], x) <= 0) break;
list[pos] = list[p];
pos = p;
}
list[pos] = x;
}
/// <summary>
/// return the minimum element and remove it
/// this is an O(log n) operation
/// </summary>
/// <returns>the minimum</returns>
public T Dequeue()
{
if (count == 0) throw new InvalidOperationException();
var value = list[0];
var x = list[--count];
list.RemoveAt(count);
if (count == 0) return value;
var pos = 0;
while (pos * 2 + 1 < count)
{
var a = 2 * pos + 1;
var b = 2 * pos + 2;
if (b < count && comp(list[b], list[a]) < 0) a = b;
if (comp(list[a], x) >= 0) break;
list[pos] = list[a];
pos = a;
}
list[pos] = x;
return value;
}
/// <summary>
/// look at the minimum element
/// this is an O(1) operation
/// </summary>
/// <returns>the minimum</returns>
public T Peek() { return list[0]; }
/// <summary>
/// clear all elements
/// this is an O(1) operation
/// </summary>
public void Clear() { list = new List<T>(); count = 0; }
/// <summary>
/// Sets the capacity to count, if count is less than a threshold value.
/// this is an O(1) operation
/// </summary>
public void TrimExcess() { list.TrimExcess(); }
/// <summary>
/// check whether item is in this queue
/// this is an O(n) operation
/// </summary>
public bool Contains(T item) { return list.Contains(item); }
void CopyTo(Array array, int index)
{
var tmp = new PriorityQueue<T>(comp, list.Count);
for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
while (!tmp.IsEmpty) array.SetValue(tmp.Dequeue(), index++);
}
bool ICollection.IsSynchronized { get { return false; } }
object ICollection.SyncRoot { get { return null; } }
public IEnumerator<T> GetEnumerator()
{
var tmp = new PriorityQueue<T>(comp, list.Count);
for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
while (!tmp.IsEmpty) yield return tmp.Dequeue();
}
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
void ICollection.CopyTo(Array array, int index) { CopyTo(array, index); }
int ICollection.Count { get { return count; } }
public bool Any() { return count > 0; }
}
class PairComparer<S, T> : IComparer<Pair<S, T>>
where S : IComparable<S>
where T : IComparable<T>
{
public PairComparer() { }
public int Compare(Pair<S, T> x, Pair<S, T> y)
{
var p = x.First.CompareTo(y.First);
if (p != 0) return p;
else return x.Second.CompareTo(y.Second);
}
}
class Pair<S, T>
{
public S First;
public T Second;
public Pair() { First = default(S); Second = default(T); }
public Pair(S s, T t) { First = s; Second = t; }
public override string ToString() { return "(" + First + ", " + Second + ")"; }
public override int GetHashCode() { return First.GetHashCode() ^ Second.GetHashCode(); }
public override bool Equals(object obj)
{
if (ReferenceEquals(this, obj)) return true;
else if (obj == null) return false;
var tmp = obj as Pair<S, T>;
return (object)tmp != null && First.Equals(tmp.First) && Second.Equals(tmp.Second);
}
}
class Point : Pair<int, int>
{
public int X { get { return First; } set { First = value; } }
public int Y { get { return Second; } set { Second = value; } }
public Point() : base(0, 0) { }
public Point(int x, int y) : base(x, y) { }
public IEnumerable<Point> Neighbors4()
{
yield return new Point(X - 1, Y);
yield return new Point(X, Y - 1);
yield return new Point(X, Y + 1);
yield return new Point(X + 1, Y);
}
public IEnumerable<Point> Neighbors8()
{
yield return new Point(X - 1, Y - 1);
yield return new Point(X - 1, Y);
yield return new Point(X - 1, Y + 1);
yield return new Point(X, Y - 1);
yield return new Point(X, Y + 1);
yield return new Point(X + 1, Y - 1);
yield return new Point(X + 1, Y);
yield return new Point(X + 1, Y + 1);
}
}
class Printer : IDisposable
{
private bool isConsole;
private TextWriter file;
public Printer() { file = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; isConsole = true; }
public Printer(string path) { file = new StreamWriter(path, false) { AutoFlush = false }; isConsole = false; }
public void Write<T>(T value) { file.Write(value); }
public void Write(string str, params object[] args) { file.Write(str, args); }
public void WriteLine() { file.WriteLine(); }
public void WriteLine<T>(T value) { file.WriteLine(value); }
public void WriteLine(string str, params object[] args) { file.WriteLine(str, args); }
public void Dispose() { file.Flush(); if (!isConsole) file.Dispose(); }
}
class Scanner : IDisposable
{
private bool isConsole;
private TextReader file;
public Scanner() { isConsole = true; file = Console.In; }
public Scanner(string path) { file = new StreamReader(path); isConsole = false; }
public void Dispose() { if (!isConsole) file.Dispose(); }
public T Get<T>() { return (T)Convert(file.ReadLine(), Type.GetTypeCode(typeof(T))); }
public Pair<S, T> Pair<S, T>() { S s; T t; Read(out s, out t); return new Pair<S, T>(s, t); }
public Tuple<S> Tuple<S>() { S s; Read(out s); return new Tuple<S>(s); }
public Tuple<S, T> Tuple<S, T>() { S s; T t; Read(out s, out t); return new Tuple<S, T>(s, t); }
public Tuple<S, T, U> Tuple<S, T, U>() { S s; T t; U u; Read(out s, out t, out u); return new Tuple<S, T, U>(s, t, u); }
public Tuple<S, T, U, V> Tuple<S, T, U, V>() { S s; T t; U u; V v; Read(out s, out t, out u, out v); return new Tuple<S, T, U, V>(s, t, u, v); }
private object Convert(string str, TypeCode type)
{
if (type == TypeCode.Int32) return int.Parse(str);
else if (type == TypeCode.UInt32) return uint.Parse(str);
else if (type == TypeCode.Int64) return long.Parse(str);
else if (type == TypeCode.UInt64) return ulong.Parse(str);
else if (type == TypeCode.Double) return double.Parse(str);
else if (type == TypeCode.Decimal) return decimal.Parse(str);
else if (type == TypeCode.String) return str;
else if (type == Type.GetTypeCode(typeof(Point))) { int s, t; Read(out s, out t); return new Point(s, t); }
else throw new Exception();
}
public T[] ReadMany<T>(int n) { var type = Type.GetTypeCode(typeof(T)); return file.ReadLine().Split().Select(str => (T)Convert(str, type)).ToArray(); }
public T[] ReadManyLines<T>(int n, Func<T> selector) { return Enumerable.Range(0, n).Select(_ => selector()).ToArray(); }
public void Read<S>(out S s)
{
var read = ReadMulti(Type.GetTypeCode(typeof(S))).ToArray();
s = (S)read[0];
}
public void Read<S, T>(out S s, out T t)
{
var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T))).ToArray();
s = (S)read[0];
t = (T)read[1];
}
public void Read<S, T, U>(out S s, out T t, out U u)
{
var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U))).ToArray();
s = (S)read[0];
t = (T)read[1];
u = (U)read[2];
}
public void Read<S, T, U, V>(out S s, out T t, out U u, out V v)
{
var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U)), Type.GetTypeCode(typeof(V))).ToArray();
s = (S)read[0];
t = (T)read[1];
u = (U)read[2];
v = (V)read[3];
}
private IEnumerable<object> ReadMulti(params TypeCode[] types)
{
var inp = file.ReadLine().Split();
for (var i = 0; i < types.Length; i++) yield return Convert(inp[i], types[i]);
}
public T[,] Board<T>(int X, int Y, Func<char, int, int, T> selector)
{
var array = new T[X, Y];
for (var y = 0; y < Y; y++)
{
var str = Get<string>();
for (var x = 0; x < X; x++) array[x, y] = selector(str[x], x, y);
}
return array;
}
}
static class Func
{
public static readonly int Inf = 1073741789; // 2 * Inf < int.MaxValue, and Inf is a prime number
/// <summary>
/// Find the first number x such that pred(x) is true
/// if pred(x) is false for all min<=x<max, then return max
/// in other words, pred(max) is assumed to be true
/// </summary>
/// <param name="min">inclusive lower limit</param>
/// <param name="max">exclusive upper limit</param>
/// <param name="pred">monotonous predicate, i.e. if pred(a) and a<b, then pred(b)</param>
/// <returns>first number such that satisfy pred</returns>
public static long FirstBinary(long min, long max, Predicate<long> pred)
{
var left = min;
var right = max;
while (left < right)
{
var mid = (left + right) >> 1;
if (pred(mid)) right = mid;
else left = mid + 1;
}
return left;
}
/// <summary>
/// Find the first number x such that pred(x) is true
/// if pred(x) is false for all min<=x<max, then return max
/// in other words, pred(max) is assumed to be true
/// </summary>
/// <param name="min">inclusive lower limit</param>
/// <param name="max">exclusive upper limit</param>
/// <param name="pred">monotonous predicate, i.e. if pred(a) and a<b, then pred(b)</param>
/// <returns>first number such that satisfy pred</returns>
public static int FirstBinary(int min, int max, Predicate<int> pred)
{
var left = min;
var right = max;
while (left < right)
{
var mid = (left + right) >> 1;
if (pred(mid)) right = mid;
else left = mid + 1;
}
return left;
}
public static void Swap<T>(this IList<T> array, int i, int j) { var tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
public static void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
public static T IndexAt<T>(this T[,] array, Pair<int, int> index) { return array[index.First, index.Second]; }
public static bool InRegion(this Pair<int, int> p, int X, int Y) { return p.InRegion(0, X, 0, Y); }
public static bool InRegion(this Pair<int, int> p, int x, int X, int y, int Y) { return p.First >= x && p.Second >= y && p.First < X && p.Second < Y; }
/// <summary>
/// get all permutation of 0, 1, ..., n - 1
/// </summary>
/// <param name="n">length of array</param>
/// <param name="func">if you want to change the elements of the array, you must take a copy</param>
public static void Permutation(int n, Action<int[]> func)
{
var array = new int[n];
var unused = new bool[n];
for (var i = 0; i < n; i++) unused[i] = true;
Permutation(n, 0, array, unused, func);
}
private static void Permutation(int n, int i, int[] array, bool[] unused, Action<int[]> func)
{
if (i == n) func(array);
else
for (var x = 0; x < n; x++)
if (unused[x])
{
array[i] = x;
unused[x] = false;
Permutation(n, i + 1, array, unused, func);
unused[x] = true;
}
}
public static long Fact(int n)
{
var fact = 1L;
for (var i = 2; i <= n; i++) fact *= i;
return fact;
}
public static long LCM(long n, long m) { return Math.Abs((n / GCD(n, m)) * m); }
public static long Divide(long n, long m) { return (n - Remainder(n, m)) / m; }
public static long Remainder(long n, long m)
{
if (m == 0) throw new DivideByZeroException();
else if (m < 0) return Remainder(n, -m);
else
{
var r = n % m;
return r < 0 ? r + m : r;
}
}
/// <summary>
/// solve nx+my=1 and returns (x,y)
/// </summary>
/// <param name="n">assumed to be with m</param>
/// <param name="m">assumed to be with n</param>
/// <returns>(x,y) where nx+my=1</returns>
public static Tuple<long, long> SolveLinear(long n, long m)
{
if (n < 0) { var p = SolveLinear(-n, m); return p == null ? p : new Tuple<long, long>(-p.Item1, p.Item2); }
if (m < 0) { var p = SolveLinear(n, -m); return p == null ? p : new Tuple<long, long>(p.Item1, -p.Item2); }
if (n < m) { var p = SolveLinear(m, n); return p == null ? p : new Tuple<long, long>(p.Item2, p.Item1); }
long a = 1, b = 0, c = 0, d = 1;
while (m > 0)
{
var r = n % m;
var q = n / m;
n = m;
m = r;
var tmp = a;
a = -a * q + b;
b = tmp;
tmp = c;
c = -c * q + d;
d = tmp;
}
return n != 1 ? null : new Tuple<long, long>(d, b);
}
public static long GCD(long n, long m)
{
var a = Math.Abs(n);
var b = Math.Abs(m);
if (a < b) { var c = a; a = b; b = c; }
while (b > 0)
{
var c = a % b;
a = b;
b = c;
}
return a;
}
public static long Inverse(long a, long mod)
{
if (a < 0) { a %= mod; if (a < 0) a += mod; }
var t = SolveLinear(a, mod);
return t.Item1;
}
public static ulong Pow(ulong a, ulong b, ulong mod)
{
var p = 1ul;
var x = a;
while (b > 0)
{
if ((b & 1) == 1) p = (p * x) % mod;
b >>= 1;
x = (x * x) % mod;
}
return p;
}
public static ulong Pow(ulong a, ulong b)
{
var p = 1ul;
var x = a;
while (b > 0)
{
if ((b & 1) == 1) p *= x;
b >>= 1;
x *= x;
}
return p;
}
public static long ChineseRemainder(Tuple<long, long> modRemainder1, Tuple<long, long> modRemainder2)
{
var m1 = modRemainder1.Item1;
var m2 = modRemainder2.Item1;
var a1 = modRemainder1.Item2;
var a2 = modRemainder2.Item2;
var t = SolveLinear(m1, m2);
var n1 = t.Item1;
var n2 = t.Item2;
return (m1 * n1 * a2 + m2 * n2 * a1) % (m1 * m2);
}
public static long ChineseRemainder(params Tuple<long, long>[] modRemainder)
{
if (modRemainder.Length == 0) throw new DivideByZeroException();
else if (modRemainder.Length == 1) return modRemainder[0].Item2;
else if (modRemainder.Length == 2) return ChineseRemainder(modRemainder[0], modRemainder[1]);
else
{
var tuple = new Tuple<long, long>(1, 0);
for (var i = 0; i < modRemainder.Length; i++)
{
var tmp = ChineseRemainder(tuple, modRemainder[i]);
tuple = new Tuple<long, long>(tuple.Item1 * modRemainder[i].Item1, tmp);
}
return tuple.Item2;
}
}
public static int MaxElement<T>(this IEnumerable<T> source, Comparison<T> comp)
{
var p = source.GetEnumerator();
if (!p.MoveNext()) return -1;
var max = p.Current;
var mi = 0;
var i = 0;
while (p.MoveNext())
{
i++;
if (comp(max, p.Current) < 0)
{
max = p.Current;
mi = i;
}
}
return mi;
}
public static int MaxElement<T>(this IEnumerable<T> source) where T : IComparable<T> { return source.MaxElement((x, y) => x.CompareTo(y)); }
public static int MinElement<T>(IEnumerable<T> source, Comparison<T> comp) { return source.MaxElement((x, y) => comp(y, x)); }
public static int MinElement<T>(IEnumerable<T> source) where T : IComparable<T> { return source.MaxElement((x, y) => y.CompareTo(x)); }
public static void Shuffle<T>(IList<T> source, Random rand) { for (var i = source.Count - 1; i >= 0; --i) source.Swap(i, rand.Next(0, i + 1)); }
public static char NextChar(this Random rand) { return (char)(rand.Next(0, 'z' - 'a' + 1) + 'a'); }
public static string NextString(this Random rand, int length) { return new string(Enumerable.Range(0, length).Select(_ => rand.NextChar()).ToArray()); }
public static IEnumerable<T> Rotate<T>(this IEnumerable<T> source)
{
var e = source.GetEnumerator();
if (e.MoveNext())
{
var f = e.Current;
while (e.MoveNext()) yield return e.Current;
yield return f;
}
}
public static T Apply<T>(this Func<T, T> func, T x, int n)
{
var a = x;
for (var i = 0; i < n; i++) a = func(a);
return a;
}
public static string ToYesNo(this bool flag) { return flag ? "YES" : "NO"; }
}