import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.function.*;
import java.text.*;
import static java.lang.Math.*;

class Util {
	static IllegalArgumentException badArgf(String fmt, Object... args) { return new IllegalArgumentException(String.format(fmt, args)); }
	static RuntimeException impossible() { return impossible(""); }
	static RuntimeException impossible(String s) { return new RuntimeException(String.format("Внутренняя ошибка%s%s.", s.isEmpty() ? "" : ": ", s)); }
	static final DecimalFormat humanFloatFormat = new DecimalFormat("#.###");
	static String humanFloat(double x) { return humanFloatFormat.format(x); }
	static String trace(Exception e) {
		StringWriter sw = new StringWriter();
		e.printStackTrace(new PrintWriter(sw));
		return sw.toString();
	}
	static double sqr(double x) { return x * x; }
}

class Vec2 {
	public final double x, y;
	public Vec2(double x, double y) { this.x = x; this.y = y; }
	public static Vec2 Vec2(double x, double y) { return new Vec2(x, y); }
	public double get(int cid) { if (cid == 0) return x; if (cid == 1) return y; throw badComponentID(cid); }
	static RuntimeException badComponentID(int cid) { return new IllegalArgumentException(String.format("Неверный индекс компонента Vec2: %d, должен быть 0 или 1.", cid)); }
	public Vec2 add(Vec2 b) { return Vec2(x + b.x, y + b.y); }
	public Vec2 sub(Vec2 b) { return Vec2(x - b.x, y - b.y); }
	public Vec2 mul(Vec2 b) { return Vec2(x * b.x, y * b.y); }
	public Vec2 mul(double b) { return Vec2(x * b, y * b); }
	public Vec2 div(Vec2 b) { return Vec2(x / b.x, y / b.y); }
	public Vec2 div(double b) { return Vec2(x / b, y / b); }
	@Override public String toString() { return String.format("(%s, %s)", Util.humanFloat(x), Util.humanFloat(y)); }
	public Vec2 min(Vec2 b) { return Vec2(Math.min(x, b.x), Math.min(y, b.y)); }
	public Vec2 max(Vec2 b) { return Vec2(Math.max(x, b.x), Math.max(y, b.y)); }
	public double length() { return sqrt(x*x + y*y); }
	public double sqrLength() { return x*x + y*y; }
	public double distanceTo(Vec2 b) { return sub(b).length(); }
	public double sqrDistanceTo(Vec2 b) { return sub(b).sqrLength(); }
	// public Vec2 normalized() { return mul(1 / length()); }
}

class Segment {
	// Пересекаются ли отрезки a0–b0 и a1–b1.
	// https://www. geeksforgeeks.org/check-if-two-given-line-segments-intersect/
	public static boolean intersects(Vec2 a0, Vec2 b0, Vec2 a1, Vec2 b1) {
		int o1 = orientation(a0, b0, a1),
			o2 = orientation(a0, b0, b1),
			o3 = orientation(a1, b1, a0),
			o4 = orientation(a1, b1, b0);
		return o1 != o2 && o3 != o4
			|| o1 == 0 && onSegment(a0, a1, b0)
			|| o2 == 0 && onSegment(a0, b1, b0)
			|| o3 == 0 && onSegment(a1, a0, b1)
			|| o4 == 0 && onSegment(a1, b0, b1);
	}

	static double cross0(Vec2 a, Vec2 b, Vec2 c) {
		return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
	}

	static int sign(double x) {
		return x > 0 ? +1 : x < 0 ? -1 : 0;
	}

	static int orientation(Vec2 a, Vec2 b, Vec2 c) {
		return sign(cross0(a, b, c));
	}

	static boolean onSegment1(double a, double x, double b) {
		return a < b ? x >= a && x <= b : x >= b && x <= a;
	}

	static boolean onSegment(Vec2 a, Vec2 p, Vec2 b) {
		return onSegment1(a.x, p.x, b.x) && onSegment1(a.y, p.y, b.y);
	}
}

// Прямоугольник со сторонами, параллельными осям координат. Легко вокруг чего-нибудь описать.
// a — минимальная точка, b — максимальная.
class AABB {
	public final Vec2 a, b;
	public AABB(Vec2 a, Vec2 b) { this.a = a; this.b = b; }
	public static AABB AABB(Vec2 a, Vec2 b) { return new AABB(a, b); }
	@Override public String toString() { return String.format("A = %s, B = %s", a, b); }

	public static AABB bound(AABB b0, AABB b1) {
		return AABB(b0.a.min(b1.a), b0.b.max(b1.b));
	}

	/*public static AABB bound(int count, IntFunction<AABB> ithBB) {
		if (count <= 0) throw Util.badArgf("AABB.bound: count = %d.", count);
		var bb = ithBB.apply(0);
		Vec2 a = bb.a, b = bb.b;
		for (int i = 1; i < count; i++) {
			bb = ithBB.apply(i);
			a = a.min(bb.a);
			b = b.max(bb.b);
		}
		return AABB(a, b);
	}*/

	public boolean contains(Vec2 p) { return p.x >= a.x && p.x <= b.x && p.y >= a.y && p.y <= b.y; }

	// Остальные 2 точки прямоугольника.
	public Vec2 bxay() { return Vec2.Vec2(b.x, a.y); }
	public Vec2 axby() { return Vec2.Vec2(a.x, b.y); }

	public boolean intersectsSegment(Vec2 a, Vec2 b) {
		Vec2 bxay = this.bxay(), axby = this.axby();
		return contains(a) || contains(b)
			// Если ни начало, ни конец отрезка не лежат внутри AABB,
			// то отрезок, пересекающий AABB, пересекает минимум 2 его стороны,
			// поэтому на самом деле достаточно проверить какие-нибудь 3, а не все 4.
			|| Segment.intersects(this.a, axby, a, b)
			|| Segment.intersects(this.a, bxay, a, b)
			|| Segment.intersects(axby, this.b, a, b)
			|| Segment.intersects(bxay, this.b, a, b);
	}

	public double sqrDistanceTo(Vec2 p) {
		return p.x < a.x ?
			p.y < a.y ? p.sqrDistanceTo(a) :
			p.y > b.y ? p.sqrDistanceTo(axby()) :
			Util.sqr(a.x - p.x) :
		p.x > b.x ?
			p.y < a.y ? p.sqrDistanceTo(bxay()) :
			p.y > b.y ? p.sqrDistanceTo(b) :
			Util.sqr(p.x - b.x)
		:
			p.y < a.y ? Util.sqr(a.y - p.y) :
			p.y > b.y ? Util.sqr(p.y - b.y) :
			0;
	}
}

// Дерево описанных объёмов (bounding volume hierarchy).
// Объекты наследуются от Item, добавляются методом add.
// Дерево перестраивается ВРУЧНУЮ методом rebuild,
// Объекты, пересечённые произвольным отрезком, запрашиваются методом castSegment.
class BVH {
	public static class Item {
		public final AABB bb;
		Item next;
		Node node;
		public Item(AABB bb) { this.bb = bb; }
	}

	// Узлы разбиваются до не более чем MIN_LEAF_NODE_SIZE объектов.
	// Также узел объединяется с родительским, если после удаления объекта
	// в нём осталось менее MIN_LEAF_NODE_SIZE объектов.
	static final int MIN_LEAF_NODE_SIZE = 3;

	// Узел с описанным объёмом bb.
	// Объекты, пережившие rebuild, содержатся в листовых узлах,
	// а добавленные с последнего вызова rebuild — в корневом
	// (так что в запросах будут проверены безусловно).
	static class Node {
		AABB bb;
		BVH bvh;
		Node left, right, parent;
		Item first, last;
		int nItems;

		// Просто добавляет объект в список, не расширяя описанный объём.
		void addToList(Item item) {
			if (item.next != null) throw Util.impossible();
			if (first == null) first = item; else last.next = item;
			last = item;
			item.node = this;
			nItems++;
		}

		// Добавляет все объекты из списка other.
		void consumeList(Node other) {
			if (other.first == null) return;
			if (first == null) first = other.first; else last.next = other.first;
			for (Item it = other.first; it != null; it = it.next) it.node = this;
			last = other.last;
			other.first = null;
			other.last = null;
			nItems += other.nItems;
			other.nItems = 0;
		}

		// Сплющивает в node содержимое узла this и его сыновей.
		void collapseTo(Node node) {
			if (this != node) node.consumeList(this);
			if (left != null) { left.collapseTo(node); left = null; }
			if (right != null) { right.collapseTo(node); right = null; }
		}

		static AABB bound(AABB b0, AABB b1) {
			return b0 == null ? b1 : AABB.bound(b0, b1);
		}

		// Перерассчитывает описанный объём. Если есть дети, то предполагается, что их объёмы уже рассчитаны.
		void recalculateBB() {
			AABB bb = null;
			for (Item it = first; it != null; it = it.next) bb = bound(bb, it.bb);
			if (left != null) bb = bound(bb, left.bb);
			if (right != null) bb = bound(bb, right.bb);
			if (bb == null) throw Util.impossible();
			this.bb = bb;
		}

		// Переразбивает node. Предполагается, что он не имеет детей, только объекты
		// (состояние после collapseTo в самого себя), и что описанный объём рассчитан.
		void divide() {
			if (left != null || right != null) throw Util.impossible();
			// после разбиения в каждом из 2 детей должно остаться MIN_LEAF_NODE_SIZE, так что
			// 2 * MIN_LEAF_NODE_SIZE — абсолютный минимум.
			// Но желательно взять больше, чтобы уменьшить шанс выполнить лишнюю работу (см. ниже).
			if (nItems < 3 * MIN_LEAF_NODE_SIZE) return;
			// разбиение по максимальному измерению
			int dim = bb.b.y - bb.a.y > bb.b.x - bb.a.x ? 1 : 0;
			// в качестве точки разбиения используется среднее арифметическое центров
			double divp = 0;
			for (Item it = first; it != null; it = it.next)
				divp += it.bb.a.get(dim) + it.bb.b.get(dim);
			divp /= 2 * nItems;

			// разделение на два узла по положению центров относительно divp
			Node nL = new Node(), nR = new Node();
			Item next = null;
			for (Item it = first; it != null; it = next) {
				next = it.next;
				it.next = null;
				if (0.5 * (it.bb.a.get(dim) + it.bb.b.get(dim)) < divp)
					nL.addToList(it);
				else
					nR.addToList(it);
			}
			this.nItems = 0;
			this.first = null;
			this.last = null;

			// Если всё хорошо, завершить изменения, пересчитать объёмы детей
			// и рекурсивно продолжить разбиение.
			if (nL.nItems >= MIN_LEAF_NODE_SIZE && nR.nItems >= MIN_LEAF_NODE_SIZE) {
				this.left = nL; nL.parent = this; nL.bvh = bvh;
				this.right = nR; nR.parent = this; nR.bvh = bvh;
				nL.recalculateBB(); nL.divide();
				nR.recalculateBB(); nR.divide();
			} else {
				// Иначе разбиение выполнено слишком сильно (но кто ж знал),
				// вернуть объекты из несостоявшихся детей в this.
				consumeList(nL);
				consumeList(nR);
			}
		}

		// Вызывает cb для объектов, пересекающих отрезок a–b.
		void castSegment(Vec2 a, Vec2 b, Consumer<Item> cb) {
			bvh._aabbXsegCalls++;
			if (!bb.intersectsSegment(a, b)) return;
			for (Item it = first; it != null; it = it.next) {
				bvh._aabbXsegCalls++;
				if (it.bb.intersectsSegment(a, b)) cb.accept(it);
			}
			if (left != null) left.castSegment(a, b, cb);
			if (right != null) right.castSegment(a, b, cb);
		}
	}

	Node root;
	int _aabbXsegCalls, _maxPqSize;

	// add просто добавляет объект в корень, так что он будет проверяться при любых запросах.
	// Он попадёт в место получше после rebuild.
	public void add(Item item) {
		if (item.node != null) throw Util.badArgf("%s уже добавлен.", item);
		if (root == null) {
			root = new Node();
			root.bb = item.bb;
			root.bvh = this;
		} else {
			root.bb = AABB.bound(root.bb, item.bb);
		}
		root.addToList(item);
		item.node = root;
	}

	public void remove(Item item) {
		Node node = item.node;
		if (node == null || node.bvh != this) throw Util.badArgf("%s не %s.", item, node == null ? "добавлен" : "в том дереве");
		// Удалить item из связного списка, хранящегося в item.node. Можно было бы не искать, если бы он был двусвязным...
		for (Item it = node.first, prev = null; it != null; prev = it, it = it.next)
			if (item == it) {
				if (prev == null) node.first = it; else prev.next = it.next;
				if (it.next == null) node.last = prev;
				node.nItems--;
				item.node = null;
				break;
			}
		if (item.node != null) throw Util.impossible("узел не найден");

		// В листовом узле стало слишком мало объектов? Удалить его, передав оставшиеся объекты родительскому.
		// Этот процесс может повториться рекурсивно.
		while (node.nItems < MIN_LEAF_NODE_SIZE && node.left == null && node.right == null) {
			if (node.parent == null) {
				if (node.nItems == 0) { node = null; root = null; }
				break;
			}
			node.parent.consumeList(node);
			if (node == node.parent.left) node.parent.left = null;
			else if (node == node.parent.right) node.parent.right = null;
			else throw Util.impossible();
			node = node.parent;
		}

		if (node != null) node.recalculateBB();
	}

	public void rebuild() {
		if (root == null) return;
		root.collapseTo(root);
		root.divide();
	}

	public void castSegment(Vec2 a, Vec2 b, Consumer<Item> cb) {
		if (root == null) return;
		root.castSegment(a, b, cb);
	}

	public List<Item> castSegment(Vec2 a, Vec2 b) {
		var r = new ArrayList<Item>();
		castSegment(a, b, it -> r.add(it));
		return r;
	}

	class QueryAroundUnion {
		boolean isNode;
		Object obj;
		double dist;

		public QueryAroundUnion(boolean isNode, Object obj, double dist) {
			this.isNode = isNode;
			this.obj = obj;
			this.dist = dist;
		}
		public QueryAroundUnion(Item it, Vec2 p) { this(false, it, it.bb.sqrDistanceTo(p)); }
		public QueryAroundUnion(Node n, Vec2 p) { this(true, n, n.bb.sqrDistanceTo(p)); }
	}

	@FunctionalInterface
	public static interface QueryAroundShoggoth {
		boolean feed(Item it, double sqrDist);
	}

	void chopBabies(Node n, PriorityQueue<QueryAroundUnion> q, Vec2 p) {
		if (n.left != null) q.add(new QueryAroundUnion(n.left, p));
		if (n.right != null) q.add(new QueryAroundUnion(n.right, p));
		for (Item it = n.first; it != null; it = it.next) q.add(new QueryAroundUnion(it, p));
		_maxPqSize = max(_maxPqSize, q.size());
	}

	public void queryAround(Vec2 p, QueryAroundShoggoth shoggoth) {
		var q = new PriorityQueue<QueryAroundUnion>(Comparator.comparingDouble(qu -> qu.dist));
		if (root != null) chopBabies(root, q, p);
		for (QueryAroundUnion qitem; null != (qitem = q.poll()); )
			if (qitem.isNode) chopBabies((Node) qitem.obj, q, p);
			else if (!shoggoth.feed((Item) qitem.obj, qitem.dist)) return;
	}

	public List<Item> queryAround(Vec2 p) {
		var r = new ArrayList<Item>();
		queryAround(p, (it, _sqrDist) -> { r.add(it); return true; });
		return r;
	}

	public String dump() {
		if (root == null) return "<empty>";
		var sb = new StringBuilder();
		sb.append("root = {\n");
		dump(root, sb, 1);
		sb.append("}");
		return sb.toString();
	}

	static StringBuilder tab(StringBuilder sb, int depth) {
		return sb.append(" ".repeat(2 * depth));
	}

	static void dump(Node node, StringBuilder sb, int depth) {
		tab(sb, depth).append(node.bb).append("\n");
		if (node.nItems != 0) {
			tab(sb, depth).append("items(").append(node.nItems).append("): ");
			for (Item it = node.first; it != null; it = it.next) {
				sb.append(it != node.first ? ", " : "").append(it);
			}
			sb.append("\n");
		}
		for (int child = 0; child < 2; child++)
			if ((child == 0 ? node.left : node.right) != null) {
				tab(sb, depth).append(child == 0 ? "left" : "right").append(" = {\n");
				dump(child == 0 ? node.left : node.right, sb, depth + 1);
				tab(sb, depth).append("}\n");
			}
	}

	int resetAabbXsegCalls() { int r = _aabbXsegCalls; _aabbXsegCalls = 0; return r; }
	int resetMaxPqSize() { int r = _maxPqSize; _maxPqSize = 0; return r; }
}

class MyItem extends BVH.Item {
	String name;
	MyItem(AABB bb, String name) { super(bb); this.name = name; }
	@Override public String toString() { return name; }
}

class Ideone
{
	static char cyclicLetter(int index) {
		final int N_LETTERS = (int)'Z' - (int)'A' + 1;
		return (char) ((int)'A' + (index % N_LETTERS + N_LETTERS) % N_LETTERS);
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		try {
			var bvh = new BVH();
			// var toRemove = new ArrayList<MyItem>();
			for (int y = 0; y < /*10*/ 100; y++) {
				for (int x = 0; x < /*10*/ 100; x++) {
					var item = new MyItem(
						AABB.AABB(
							Vec2.Vec2(x+0.2, y+0.2),
							Vec2.Vec2(x+0.8, y+0.8)),
						"" + cyclicLetter(x) + cyclicLetter(y));
					// if ((x + y) % 2 < 1) toRemove.add(item);
					bvh.add(item);
				}
			}

			Vec2 segA = Vec2.Vec2(2, 4.3), segB = Vec2.Vec2(7, 3.3);

			System.out.println("1. Запрос на неперестроенном дереве.");
			System.out.printf("%s\n", bvh.castSegment(segA, segB));
			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());
			// String treeDump0 = bvh.dump();

			bvh.rebuild();
			System.out.println("2. Запрос на перестроенном дереве.");
			System.out.printf("%s\n", bvh.castSegment(segA, segB));
			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());
			// String treeDump1 = bvh.dump();

			/*for (var rem: toRemove) bvh.remove(rem);
			System.out.printf("3. Запрос после равномерного удаления %d элементов.\n", toRemove.size());
			System.out.printf("%s\n", bvh.castSegment(segA, segB));
			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());*/

			Vec2 epicenter = Vec2.Vec2(7.5, 6.5); // HG
			/*System.out.printf("3. Сортировка по расстоянию от точки %s.\n", epicenter);
			bvh.queryAround(epicenter, (it, sqrDist) -> {
				System.out.printf("%s (%s)\n", it, Util.humanFloat(sqrt(sqrDist)));
				return true;
			});
			System.out.printf("Максимальное число элементов очереди: %d.\n\n", bvh.resetMaxPqSize());*/

			double radius = 3;
			System.out.printf("3. Сортировка по расстоянию от точки %s, макс. радиус %s.\n", epicenter, Util.humanFloat(radius));
			bvh.queryAround(epicenter, (it, sqrDist) -> {
				if (sqrDist > radius * radius) return false;
				System.out.printf("%s (%s)\n", it, Util.humanFloat(sqrt(sqrDist)));
				return true;
			});
			System.out.printf("Максимальное число элементов очереди: %d.\n\n", bvh.resetMaxPqSize());

			/*System.out.printf("Дамп дерева после шага 1:\n%s\n\n", treeDump0);
			System.out.printf("Дамп дерева после шага 2:\n%s\n\n", treeDump1);*/
		} catch (Exception e) {
			System.out.println(Util.trace(e));
		}
	}
}