Problem: No Great Victory anniversary in Berland has ever passed without the war parade. This year is not an exception. That’s why the preparations are on in full strength. Tanks are building a line, artillery mounts are ready to fire, soldiers are marching on the main square... And the air forces general Mr. Generalov is in trouble again. This year a lot of sky-scrapers have been built which makes it difficult for the airplanes to fly above the city. It was decided that the planes should fly strictly from south to north. Moreover, there must be no sky scraper on a plane’s route, otherwise the anniversary will become a tragedy. The Ministry of Building gave the data on n sky scrapers (the rest of the buildings are rather small and will not be a problem to the planes). When looking at the city from south to north as a geometrical plane, the i-th building is a rectangle of height hi. Its westernmost point has the x-coordinate of li and the easternmost — of ri. The terrain of the area is plain so that all the buildings stand on one level. Your task as the Ministry of Defence’s head programmer is to find an enveloping polyline using the data on the sky-scrapers. The polyline’s properties are as follows:

  * If you look at the city from south to north as a plane, then any part of any building will be inside or on the boarder of the area that the polyline encloses together with the land surface. 
  * The polyline starts and ends on the land level, i.e. at the height equal to 0. 
  * The segments of the polyline are parallel to the coordinate axes, i.e. they can only be vertical or horizontal. 
  * The polyline’s vertices should have integer coordinates. 
  * If you look at the city from south to north the polyline (together with the land surface) must enclose the minimum possible area. 
  * The polyline must have the smallest length among all the polylines, enclosing the minimum possible area with the land. 
  * The consecutive segments of the polyline must be perpendicular. 

<image> Picture to the second sample test (the enveloping polyline is marked on the right). 

Input

The first input line contains integer n (1 ≤ n ≤ 100000). Then follow n lines, each containing three integers hi, li, ri (1 ≤ hi ≤ 109, - 109 ≤ li < ri ≤ 109).

Output

In the first line output integer m — amount of vertices of the enveloping polyline. The next m lines should contain 2 integers each — the position and the height of the polyline’s vertex. Output the coordinates of each vertex in the order of traversing the polyline from west to east. Remember that the first and the last vertices of the polyline should have the height of 0.

Examples

Input

2
3 0 2
4 1 3


Output

6
0 0
0 3
1 3
1 4
3 4
3 0


Input

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8


Output

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

//Codeforces Beta Round #35 (Div. 2), E
public class Parade {

	private static class Interval implements Comparable<Interval> {
		final int start, end, height;
		Interval(int start, int end, int height) {
			this.start = start;
			this.end = end;
			this.height = height;
		}
		@Override
		public int hashCode() {
			return start ^ end ^ height;
		}
		private int address() {
			return super.hashCode();
		}
		public int compareTo(Interval o) {
			int result = height - o.height;
			if(result != 0)
				return result;
			return address() - o.address();
		}
		int index;
		//Interval parent, left, right;
		//boolean color;
	}
	//private static class Point2 extends Point {
	private static class Point2 implements Comparable<Point2> {
		int x, h;
		@Override
		public String toString() {
			return x + " " + h;
		}
		Point2(int x, int h) {
			this.x = x;
			this.h = h;
		}
		boolean end;
		Interval interval;
		Point2(Interval interval, boolean end) {
			this(end ? interval.end : interval.start, 0);
			this.end = end;
			this.interval = interval;
		}
		//public int compareTo(Point o) {
		//	return compareTo((Point2)o);
		//}
		public int compareTo(Point2 o) {
			int result = x - o.x;
			if(result != 0)
				return result;
			if(!end) {
				if(!o.end) {
					result = interval.height - o.interval.height;
					return result != 0 ? result : interval.address() - o.interval.address();
				} else
					return 1;
			} else {
				if(!o.end)
					return -1;
				else {
					result = o.interval.height - interval.height;
					return result != 0 ? result : o.interval.address() - interval.address();
				}
			}
		}
	}

	public static List<Point2> solve4(BufferedReader reader) throws IOException {
		int n = Integer.parseInt(reader.readLine());
		Interval buildings[] = new Interval[n];
		Point2 points[] = new Point2[n * 2];
		for(int i = 0; i < n; i++) {
			String[] s = reader.readLine().split(" ");
			assert s.length == 3;
			int h = Integer.parseInt(s[0]), left = Integer.parseInt(s[1]), right = Integer.parseInt(s[2]);
			assert left < right;
			buildings[i] = new Interval(left, right, h);
			points[i] = new Point2(buildings[i], false);
			points[n + i] = new Point2(buildings[i], true);
		}
		reader.close();
		//System.gc();

		qsort(/*(Point[])*/ points);
		qsort(buildings);
		for(int i = 0; i < buildings.length; i++)
			buildings[i].index = i;
		{
			boolean heights[] = new boolean[buildings.length];
			//short m = (short)Math.round(Math.sqrt(n)), index[] = new short[(n - 1) / m + 1];
			int top = -1, bottom = n, max = 0;
			for(int i = 0; i < points.length; i++) {
				Point2 point = points[i];
				if(!point.end) {
					heights[point.interval.index] = true;
					top = Math.max(top, point.interval.index);
					max = Math.max(max, point.interval.height);
					bottom = Math.min(bottom, point.interval.index);
					//index[point.interval.index / m]++;
				} else {
					heights[point.interval.index] = false;
					//index[point.interval.index / m]--;
					if(max == point.interval.height) {
						max = 0;
						/*if(index[top / m] == 0) {
							for(top = top / m - 1; top >= 0 && index[top] == 0; top--);
							if(top >= 0)
								top = (top + 1) * m - 1;
						}*/
						for(int j = top; j >= bottom; j--) {
							if(heights[j]) {
								max = buildings[top = j].height;
								break;
							}
						}
						if(max == 0) {
							bottom = n;
							top = -1;
						}
					}
				}
				if(i != 0 && points[i - 1].x == point.x)
					points[i - 1] = null;
				point.h = max;
			}
		}
		//System.gc();

		List<Point2> result = new LinkedList<Point2>();
		Point2 prev = null;
		for(Point2 point : points) {
			if(point == null || prev != null && point.h == prev.h)
				continue;
			if(prev == null)
				result.add(prev = new Point2(point.x, 0));
			assert !point.end || point.h < prev.h;
			if(point.h != prev.h && point.x != prev.x)
				result.add(new Point2(point.x, prev.h));
			result.add(prev = point);
		}
		return result;
	}

	public static List<Point2> solve2(BufferedReader reader) throws IOException {
		int n = Integer.parseInt(reader.readLine());
		Point2 points[] = new Point2[n * 2];
		for(int i = 0; i < n; i++) {
			String[] s = reader.readLine().split(" ");
			assert s.length == 3;
			int h = Integer.parseInt(s[0]), left = Integer.parseInt(s[1]), right = Integer.parseInt(s[2]);
			assert left < right;
			Interval building = new Interval(left, right, h);
			points[i] = new Point2(building, false);
			points[n + i] = new Point2(building, true);
		}
		reader.close();

		qsort(/*(Point[])*/ points);

		{
			SortedSet<Interval> set = new TreeSet<Interval>();
			//IntervalSet set = new IntervalSet();
			int max = 0;
			for(int i = 0; i < points.length; i++) {
				Point2 point = points[i];
				if(!point.end) {
					set.add(point.interval);
					max = Math.max(max, point.interval.height);
				} else {
					set.remove(point.interval);
					if(max == point.interval.height)
						max = !set.isEmpty() ? set.last().height : 0;
				}
				if(i != 0 && points[i - 1].x == point.x)
					points[i - 1] = null;
				point.h = max;
			}
		}
		System.gc();

		List<Point2> result = new LinkedList<Point2>();
		Point2 prev = null;
		for(Point2 point : points) {
			if(point == null || prev != null && point.h == prev.h)
				continue;
			if(prev == null)
				result.add(prev = new Point2(point.x, 0));
			assert !point.end || point.h < prev.h;
			if(point.h != prev.h && point.x != prev.x)
				result.add(new Point2(point.x, prev.h));
			result.add(prev = point);
		}
		return result;
	}

	public static void main(String[] args) throws IOException {
		/*IntervalSet set = new IntervalSet();
		Random random = new Random();
		for(int i = 0; i < 1000000; i++)
			set.add(new Interval(random.nextInt(100), random.nextInt(100), random.nextInt(100)));
		System.out.println(set.count());
		System.out.println(set.validate());
		if(true) return;
		/**/
		//test34();
		//test35();
		//for(int i = 0; i < 10; i++) test();
		System.setIn(new FileInputStream("input.txt"));
		System.setOut(new PrintStream("output.txt"));
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		List<? extends Object> result = solve4(reader);
		//System.gc();
		System.out.println(result.size());
		for(Object p : result)
			System.out.println(p);
	}

	public static void test1() throws IOException {
		Random random = new Random(1);
		int n = 10; //1 + random.nextInt(100000);
		StringBuilder sb = new StringBuilder();
		sb.append(n).append('\n');
		for(int i = 0; i < n; i++) {
			sb.append(1 + random.nextInt((int)100)).append(' ');
			int left = 100 - random.nextInt((int)100);
			sb.append(left).append(' ');
			sb.append(left + 1 + random.nextInt((int)100)).append('\n');
		}
		char a[] = sb.toString().toCharArray();
		long startTime = System.currentTimeMillis();
		List<Point2> result2 = solve4(new BufferedReader(new CharArrayReader(a)));
		long time2 = -(startTime - (startTime = System.currentTimeMillis()));
		List<Point> result1 = solve1(new BufferedReader(new CharArrayReader(a)));
		long time1 = System.currentTimeMillis() - startTime;
		System.out.println(time2 + "/" + time1);
		//assert Arrays.equals(result1.toArray(), result2.toArray());
	}

	public static void test() throws IOException {
		Random random = new Random(1);
		int n = 100000; //1 + random.nextInt(100000);
		StringBuilder sb = new StringBuilder();
		sb.append(n).append('\n');
		for(int i = 0; i < n; i++) {
			sb.append(1 + random.nextInt((int)10e8)).append(' ');
			int left = (int)10e8 / 2 - random.nextInt((int)10e8);
			sb.append(left).append(' ');
			sb.append(left + 1 + random.nextInt((int)10e8)).append('\n');
		}
		char a[] = sb.toString().toCharArray();
		long startTime = System.currentTimeMillis();
		List<Point2> result2 = solve4(new BufferedReader(new CharArrayReader(a)));
		long time2 = -(startTime - (startTime = System.currentTimeMillis()));
		List<Point> result1 = solve1(new BufferedReader(new CharArrayReader(a)));
		long time1 = System.currentTimeMillis() - startTime;
		System.out.println(time2 + "/" + time1);
		//assert Arrays.equals(result1.toArray(), result2.toArray());
	}

	public static void test34() throws IOException {
		int n = 100000;
		StringBuilder sb = new StringBuilder();
		sb.append(n).append('\n');
		for(int i = 0; i < n; i++) {
			sb.append(1 + i).append(' ');
			sb.append(i - 1000000000).append(' ');
			sb.append(1000000000 - i).append('\n');
		}
		char a[] = sb.toString().toCharArray();
		long startTime = System.currentTimeMillis();
		solve4(new BufferedReader(new CharArrayReader(a)));
		long time2 = System.currentTimeMillis() - startTime;
		System.out.println(time2);
	}

	public static void test35() throws IOException {
		int n = 100000;
		StringBuilder sb = new StringBuilder();
		sb.append(n).append('\n');
		for(int i = 0; i < n; i++) {
			sb.append(i * 10000 + 1).append(' ');
			sb.append(i * 10000 - 1000000000).append(' ');
			sb.append(1000000000 - i * 10000).append('\n');
		}
		char a[] = sb.toString().toCharArray();
		long startTime = System.currentTimeMillis();
		solve4(new BufferedReader(new CharArrayReader(a)));
		long time2 = System.currentTimeMillis() - startTime;
		System.out.println(time2);
	}

	private static class Point implements Comparable<Point> {
		protected int x, h;
		Point(int x, int h) {
			this.x = x;
			this.h = h;
		}
		public int compareTo(Point o) {
			int result = x - o.x;
			if(result != 0)
				return result;
			return h - o.h;
		}
		@Override
		public String toString() {
			return x + " " + h;
		}
		@Override
		public boolean equals(Object o) {
			return o instanceof Point && equals((Point)o);
		}
		public boolean equals(Point o) {
			return x == o.x && h == o.h;
		}
	}
	public static List<Point> solve1(BufferedReader reader) throws IOException {
		int n = Integer.parseInt(reader.readLine());
		List<Point> list = new ArrayList<Point>(2 * (n + 1));
		list.add(new Point(Integer.MIN_VALUE, 0));
		list.add(new Point(Integer.MAX_VALUE, 0));
		for(; n > 0; n--) {
			String[] s = reader.readLine().split(" ");
			assert s.length == 3;
			int h = Integer.parseInt(s[0]), left = Integer.parseInt(s[1]), right = Integer.parseInt(s[2]);
			assert left < right;
			boolean b = false;
			int ph = 0;
			for(ListIterator<Point> iterator = list.listIterator(Math.max(0, -2 - Collections.binarySearch(list, new Point(left, -1)))); iterator.hasNext();) {
				Point p = iterator.next();
				if(p.x >= left && !b) {
					iterator.previous();
					Point t = iterator.previous();
					iterator.next();
					if(p.x != left && t.h < h)
						iterator.add(new Point(left, h));
					iterator.next();
					b = true;
					ph = t.h;
				}
				if(b) {
					if(p.x >= right) {
						if(p.x != right && ph < h) {
							iterator.set(new Point(right, ph));
							iterator.add(p);
						}
						break;
					}
					ph = p.h;
					if(h > p.h)
						p.h = h;
				}
			}
		}
		assert list.size() >= 4 && list.get(0).x == Integer.MIN_VALUE && list.get(list.size() - 1).x == Integer.MAX_VALUE;
		List<Point> result = new LinkedList<Point>();
		Point prev = null;
		for(Point p : list) {
			if(prev != null && p.h == prev.h)
				continue;
			if(prev != null && p.h != prev.h && p.x != prev.x)
				result.add(new Point(p.x, prev.h));
			if(p.x != Integer.MIN_VALUE && p.x != Integer.MAX_VALUE)
				result.add(p);
			prev = p;
		}
		return result;
	}

	public static List<Point2> solve3(BufferedReader reader) throws IOException {
		int n = Integer.parseInt(reader.readLine());
		Interval buildings[] = new Interval[n];
		Point2 points[] = new Point2[n * 2];
		for(int i = 0; i < n; i++) {
			String[] s = reader.readLine().split(" ");
			assert s.length == 3;
			int h = Integer.parseInt(s[0]), left = Integer.parseInt(s[1]), right = Integer.parseInt(s[2]);
			assert left < right;
			buildings[i] = new Interval(left, right, h);
			points[i] = new Point2(buildings[i], false);
			points[n + i] = new Point2(buildings[i], true);
		}

		qsort(/*(Point[])*/points);

		for(int i = 0; i < n; i++) {
			int start = Arrays.binarySearch(points, new Point2(buildings[i], false));
			int end = Arrays.binarySearch(points, new Point2(buildings[i], true));
			for(int j = start; j < end; j++) {
				points[j].h = Math.max(points[j].h, buildings[i].height);
			}
		}
		for(int i = 1; i < points.length; i++) {
			if(points[i - 1].x == points[i].x)
				points[i - 1] = null;
		}

		List<Point2> result = new LinkedList<Point2>();
		Point2 prev = null;
		for(Point2 point : points) {
			if(point == null || prev != null && point.h == prev.h)
				continue;
			if(prev == null)
				result.add(prev = new Point2(point.x, 0));
			assert !point.end || point.h < prev.h;
			if(point.h != prev.h && point.x != prev.x)
				result.add(new Point2(point.x, prev.h));
			result.add(prev = point);
		}
		return result;
	}

	private static final int H[] = new int[] {1, 4, 9, 24, 85, 126};
	private static <T extends Comparable<T>> void ssort(T[] a, int lo, int hi) {
		for(int k = H.length - 1; k >= 0; k--) {
			for(int h = H[k], i = lo + h, j; i <= hi; i++) {
				T m = a[i];
				for(j = i - h; j >= lo && a[j].compareTo(m) > 0; j -= h)
					a[j + h] = a[j];
				a[j + h] = m;
			}
		}
	}
	private static <T extends Comparable<T>> void qsort(T[] a) {
		qsort(a, 0, a.length - 1);
	}
	private static <T extends Comparable<T>> void qsort(T[] a, int lo, int hi) {
		for(;;) {
			if(hi - lo < 256) {
				ssort(a, lo, hi);
				return;
			}
			int i = lo, j = hi;
			for(T m = a[(lo + hi) / 2];;) {
				while(i < hi && a[i].compareTo(m) < 0)
					i++;
				while(j > lo && a[j].compareTo(m) > 0)
					j--;
				if(i >= j)
					break;
				T t = a[i]; a[i++] = a[j]; a[j--] = t;
			}
			if((--i - lo) < (hi - ++j)) {
				qsort(a, lo, i);
				lo = j;
			} else {
				qsort(a, j, hi);
				hi = i;
			}
		}
	}

	/*private static class IntervalSet {
		private Interval root;
		private static int validate(Interval r) {
			int black;
			if(r.left != null) {
				if(r.left.parent != r)
					return -1;
				if(r.color && r.left.color)
					return -1;
				if((black = validate(r.left)) < 0)
					return -1;
			} else
				black = 0;
			if(r.right != null) {
				if(r.right.parent != r)
					return -1;
				if(r.color && r.right.color)
					return -1;
				if(black != validate(r.right))
					return -1;
			} else if(black != 0)
				return -1;
			return black + (r.color ? 0 : 1);
		}
		protected boolean validate() {
			if(root != null) {
				if(root.parent != null)
					return false;
				System.out.println(validate(root));
				return validate(root) >= 0;
			}
			return true;
		}
		private static int count(Interval r) {
			return r != null ? 1 + count(r.left) + count(r.right) : 0;
		}
		protected int count() {
			return count(root);
		}
		private void leftRotate(Interval x) {
			Interval y = x.right;
			if((x.right = y.left) != null)
				y.left.parent = x;
			if((y.parent = x.parent) == null)
				root = y;
			else {
				if(x.parent.left == x)
					x.parent.left = y;
				else
					x.parent.right = y;
			}
			y.left = x;
			x.parent = y;
		}
		private void rightRotate(Interval x) {
			Interval y = x.left;
			if((x.left = y.right) != null)
				y.right.parent = x;
			if((y.parent = x.parent) == null)
				root = y;
			else {
				if(x.parent.left == x)
					x.parent.left = y;
				else
					x.parent.right = y;
			}
			y.right = x;
			x.parent = y;
		}
		private void insertFixup(Interval x) {
			x.color = true;
			while(x != root && x.parent.color) {
				if(x.parent == x.parent.parent.left) {
					Interval y = x.parent.parent.right;
					if(y != null && y.color) {
						x.parent.color = false;
						y.color = false;
						x.parent.parent.color = true;
						x = x.parent.parent;
					} else {
						if(x.parent.right == x)
							leftRotate(x = x.parent);
						x.parent.color = false;
						x.parent.parent.color = true;
						rightRotate(x.parent.parent);
					}
				} else {
					Interval y = x.parent.parent.left;
					if(y != null && y.color) {
						x.parent.color = false;
						y.color = false;
						x.parent.parent.color = true;
						x = x.parent.parent;
					} else {
						if(x.parent.left == x)
							rightRotate(x = x.parent);
						x.parent.color = false;
						x.parent.parent.color = true;
						leftRotate(x.parent.parent);
					}

				}
			}
			root.color = false;
		}
		public boolean add(Interval e) {
			if(root == null) {
				root = e;
				return true;
			} else {
				Interval i = root;
				for(;;) {
					int diff = e.compareTo(i);
					if(diff < 0) {
						if(i.left == null) {
							(e.parent = i).left = e;
							insertFixup(e);
							return true;
						} else
							i = i.left;
					} else if(diff > 0) {
						if(i.right == null) {
							(e.parent = i).right = e;
							insertFixup(e);
							return true;
						} else
							i = i.right;
					} else
						return false;
				}
			}
		}
		private void deleteFixup(Interval x) {

		}
		public void remove(Interval e) {
			if(e.left == null) {
				if(e.right == null) {
					if(e.parent == null)
						root = null;
					else if(e.parent.left == e)
						e.parent.left = null;
					else
						e.parent.right = null;
				} else {
					if(e.parent == null)
						root = e.right;
					else if(e.parent.left == e)
						e.parent.left = e.right;
					else
						e.parent.right = e.right;
					e.right.parent = e.parent;
				}
			} else {
				if(e.right == null) {
					if(e.parent == null)
						root = e.left;
					else if(e.parent.left == e)
						e.parent.left = e.left;
					else
						e.parent.right = e.left;
					e.left.parent = e.parent;
				} else {
					Interval i = e.right;
					if(i.left != null) {
						do
							i = i.left;
						while(i.left != null);
						assert i.parent.left == i;
						i.parent.left = i.right;
						if(i.right != null)
							i.right.parent = i.parent;
						i.right = e.right;
						e.right.parent = i;
					}
					i.parent = e.parent;
					if(e.parent != null) {
						if(e.parent.left == e)
							e.parent.left = i;
						else
							e.parent.right = i;
					} else
						root = i;
					i.left = e.left;
					if(e.left != null)
						e.left.parent = i;
				}
			}
			e.parent = e.left = e.right = null;
		}
		public Interval last() {
			if(root == null)
				return null;
			Interval i = root;
			while(i.right != null)
				i = i.right;
			return i;
		}
		public boolean isEmpty() {
			return root == null;
		}
	}*/
}