#358279 (Java21) No.855 ヘビの日光浴

提出ソース
結果

問題	No.855 ヘビの日光浴
ユーザー	CuriousFairy315
提出日時	2019-07-09 01:01:24
言語	Java21 (openjdk 21)
結果	WA (最新) AC (最初)
実行時間	-
コード長	44,692 bytes
コンパイル時間	3,741 ms
コンパイル使用メモリ	99,500 KB
実行使用メモリ	75,404 KB
最終ジャッジ日時	2024-10-01 20:40:39
合計ジャッジ時間	30,129 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	82 ms 38,524 KB
testcase_01	AC	76 ms 38,340 KB
testcase_02	AC	74 ms 38,252 KB
testcase_03	AC	78 ms 38,304 KB
testcase_04	AC	79 ms 38,236 KB
testcase_05	AC	78 ms 38,464 KB
testcase_06	AC	78 ms 38,392 KB
testcase_07	AC	80 ms 38,500 KB
testcase_08	AC	83 ms 38,468 KB
testcase_09	AC	89 ms 38,344 KB
testcase_10	AC	83 ms 38,268 KB
testcase_11	AC	83 ms 38,656 KB
testcase_12	AC	79 ms 38,360 KB
testcase_13	AC	83 ms 38,380 KB
testcase_14	AC	92 ms 38,220 KB
testcase_15	AC	78 ms 38,184 KB
testcase_16	AC	82 ms 38,612 KB
testcase_17	AC	79 ms 38,688 KB
testcase_18	AC	90 ms 38,436 KB
testcase_19	AC	88 ms 38,500 KB
testcase_20	AC	79 ms 38,104 KB
testcase_21	AC	86 ms 38,448 KB
testcase_22	AC	88 ms 38,212 KB
testcase_23	AC	87 ms 38,212 KB
testcase_24	AC	87 ms 38,348 KB
testcase_25	AC	82 ms 38,672 KB
testcase_26	AC	79 ms 38,340 KB
testcase_27	AC	76 ms 38,304 KB
testcase_28	AC	81 ms 38,332 KB
testcase_29	AC	84 ms 38,388 KB
testcase_30	AC	79 ms 38,512 KB
testcase_31	AC	92 ms 38,368 KB
testcase_32	AC	83 ms 38,488 KB
testcase_33	AC	130 ms 39,208 KB
testcase_34	AC	116 ms 39,280 KB
testcase_35	AC	108 ms 38,940 KB
testcase_36	AC	109 ms 39,124 KB
testcase_37	AC	127 ms 38,844 KB
testcase_38	WA	-
testcase_39	AC	107 ms 39,016 KB
testcase_40	AC	124 ms 39,924 KB
testcase_41	AC	120 ms 39,448 KB
testcase_42	AC	109 ms 38,972 KB
testcase_43	AC	91 ms 38,756 KB
testcase_44	AC	128 ms 39,548 KB
testcase_45	AC	122 ms 39,320 KB
testcase_46	AC	127 ms 39,340 KB
testcase_47	AC	106 ms 39,568 KB
testcase_48	WA	-
testcase_49	AC	109 ms 39,404 KB
testcase_50	AC	125 ms 39,576 KB
testcase_51	AC	109 ms 39,516 KB
testcase_52	AC	98 ms 39,068 KB
testcase_53	AC	85 ms 38,280 KB
testcase_54	WA	-
testcase_55	AC	82 ms 38,476 KB
testcase_56	WA	-
testcase_57	AC	82 ms 38,448 KB
testcase_58	AC	81 ms 38,288 KB
testcase_59	AC	81 ms 38,508 KB
testcase_60	AC	92 ms 38,544 KB
testcase_61	AC	81 ms 38,364 KB
testcase_62	WA	-
testcase_63	AC	80 ms 38,596 KB
testcase_64	WA	-
testcase_65	AC	85 ms 38,216 KB
testcase_66	AC	84 ms 38,664 KB
testcase_67	AC	71 ms 38,296 KB
testcase_68	AC	82 ms 38,560 KB
testcase_69	AC	82 ms 38,344 KB
testcase_70	AC	81 ms 38,528 KB
testcase_71	AC	96 ms 38,316 KB
testcase_72	AC	83 ms 38,516 KB
testcase_73	AC	594 ms 57,304 KB
testcase_74	AC	587 ms 56,904 KB
testcase_75	AC	418 ms 53,752 KB
testcase_76	AC	825 ms 68,516 KB
testcase_77	AC	722 ms 69,964 KB
testcase_78	AC	875 ms 69,088 KB
testcase_79	AC	209 ms 45,964 KB
testcase_80	AC	228 ms 45,300 KB
testcase_81	AC	946 ms 71,920 KB
testcase_82	AC	972 ms 74,976 KB
testcase_83	AC	992 ms 75,344 KB
testcase_84	AC	1,038 ms 75,400 KB
testcase_85	WA	-
testcase_86	AC	1,007 ms 75,272 KB
testcase_87	AC	994 ms 72,420 KB
testcase_88	AC	991 ms 71,944 KB
testcase_89	AC	987 ms 75,204 KB
testcase_90	AC	995 ms 74,688 KB
testcase_91	AC	1,025 ms 75,404 KB
testcase_92	AC	993 ms 71,480 KB
testcase_93	AC	81 ms 38,092 KB
testcase_94	AC	630 ms 74,196 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
package yukicoder_2897;

import java.awt.Point;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.TreeMap;
import java.util.function.Predicate;

public class Main {

	public static void main(String[] args) {
		new Main();
	}

	private static class Direction{
		public static final int DOWN = 0, LEFT = 1, UP = 2, RIGHT = 3;
	}

	private class Snake{
		private int direction;
		private int point, length;
		public Snake(int H, int W, int X, int Y, int L) {
			if (!IntRange.closed(1, 1000000000).contains(L)) System.exit(1);
			if (!IntRange.closed(1, W).contains(X)) {
				if (!IntRange.closed(1, 1000000000).contains(Y))System.exit(1);
				if (X == 0) {
					direction = Direction.LEFT;
					point = Y;
					length = L;
				} else if (X == W + 1) {
					direction = Direction.RIGHT;
					point = Y;
					length = L;
				} else System.exit(1);
			} else {
				if (!IntRange.closed(1, 1000000000).contains(X))System.exit(1);
				if (Y == 0) {
					direction = Direction.UP;
					point = X;
					length = L;
				} else if (Y == H + 1) {
					direction = Direction.DOWN;
					point = X;
					length = L;
				} else System.exit(1);
			}
		}

		public int getDirection() {
			return direction;
		}

		public int getPoint() {
			return point;
		}

		public int getLength() {
			return length;
		}
	}

	public Main() {
		FastIO io = new FastIO();
		int H = io.nextInt(), W = io.nextInt(), N = io.nextInt();
		if (!IntRange.closed(1, 1000000000).contains(H)) System.exit(1);
		if (!IntRange.closed(1, 1000000000).contains(W)) System.exit(1);
		if (!IntRange.closed(1, 100000).contains(N)) System.exit(1);
		Snake[] snake = new Snake[N];
		ArrayList<Integer> comp = new ArrayList<>();
		for (int i : IntRange.open(N)) {
			snake[i] = new Snake(H, W, io.nextInt(), io.nextInt(), io.nextInt());
			comp.add(snake[i].getPoint());
		}
		comp.add(0);
		comp.add(1000000001);
		CompressTree<Integer> compress = new CompressTree<>(comp);
		CircularArray<SegmentTree<Integer>> segment = new CircularArray<>(4);
		for (int d : IntRange.open(4)) {
			segment.setFront(new SegmentTree<>(compress.size(), 0, (i, j) -> Math.max(i, j)));
			segment.rotateNext();
		}
		for (int i : IntRange.open(N)) {
			int index = compress.zip(snake[i].getPoint()), direction = snake[i].getDirection();
			int sumLength = segment.get(direction).get(index) + snake[i].getLength();
			int lenIndex = compress.floorZip(sumLength) + 1;
			int left, right;
			switch(direction) {
				case Direction.UP:
					left = segment.get(direction - 1).binarySearch(0, lenIndex, l -> l < snake[i].getPoint()) + 1;
					right = segment.get(direction + 1).binarySearch(0, lenIndex, l -> l < W + 1 - snake[i].getPoint()) + 1;
					if (left < right) {
						segment.get(direction).update(0, index);
						segment.get(direction - 1).update(0, left);
					} else if (left > right) {
						segment.get(direction).update(0, index);
						segment.get(direction + 1).update(0, right);
					} else if (segment.get(direction + 2).get(index) + sumLength > H) {
						segment.get(direction + 2).update(0, index);
						segment.get(direction).update(0, index);
					} else {
						segment.get(direction).update(sumLength, index);
					}
					break;
				case Direction.LEFT:
					left = segment.get(direction - 1).binarySearch(0, lenIndex, l -> l < H + 1 - snake[i].getPoint()) + 1;
					right = segment.get(direction + 1).binarySearch(0, lenIndex, l -> l < snake[i].getPoint()) + 1;
					if (left < right) {
						segment.get(direction).update(0, index);
						segment.get(direction - 1).update(0, left);
					} else if (left > right) {
						segment.get(direction).update(0, index);
						segment.get(direction + 1).update(0, right);
					} else if (segment.get(direction + 2).get(index) + sumLength > W) {
						segment.get(direction + 2).update(0, index);
						segment.get(direction).update(0, index);
					} else {
						segment.get(direction).update(sumLength, index);
					}
					break;
				case Direction.DOWN:
					lenIndex = compress.ceilingZip(H - sumLength) + 1;
					left = segment.get(direction - 1).binarySearch(compress.size(), lenIndex, l -> l < W + 1 - snake[i].getPoint()) - 1;
					right = segment.get(direction + 1).binarySearch(compress.size(), lenIndex, l -> l < snake[i].getPoint()) - 1;
					if (left < right) {
						segment.get(direction).update(0, index);
						segment.get(direction + 1).update(0, right);
					} else if (left > right) {
						segment.get(direction).update(0, index);
						segment.get(direction - 1).update(0, left);
					} else if (segment.get(direction + 2).get(index) + sumLength > H) {
						segment.get(direction + 2).update(0, index);
						segment.get(direction).update(0, index);
					} else {
						segment.get(direction).update(sumLength, index);
					}
					break;
				case Direction.RIGHT:
					lenIndex = compress.ceilingZip(W - sumLength) + 1;
					left = segment.get(direction - 1).binarySearch(compress.size(), lenIndex, l -> l < snake[i].getPoint()) - 1;
					right = segment.get(direction + 1).binarySearch(compress.size(), lenIndex, l -> l < H + 1 - snake[i].getPoint()) - 1;
					if (left < right) {
						segment.get(direction).update(0, index);
						segment.get(direction + 1).update(0, right);
					} else if (left > right) {
						segment.get(direction).update(0, index);
						segment.get(direction - 1).update(0, left);
					} else if (segment.get(direction + 2).get(index) + sumLength > W) {
						segment.get(direction + 2).update(0, index);
						segment.get(direction).update(0, index);
					} else {
						segment.get(direction).update(sumLength, index);
					}
					break;
			}
			/* デバッグ用、描画可視化
			io.print("turn:" + i + " snake:(");
			switch(direction) {
				case Direction.UP:
					io.print(snake[i].getPoint() + ", 0)");
					break;
				case Direction.LEFT:
					io.print("0, " + snake[i].getPoint() + ")");
					break;
				case Direction.RIGHT:
					io.print((W + 1) + ", " + snake[i].getPoint() + ")");
					break;
				case Direction.DOWN:
					io.print(snake[i].getPoint() + ", " + (H + 1) + ")");
					break;
			}
			io.println(": " + snake[i].getLength());
			io.print("*");
			for (int n = 1;n <= W;++ n) io.print(" " + (compress.hasZip(n) ? segment.get(Direction.UP).get(compress.zip(n)) : 0));
			io.println(" *");
			for (int n = 1;n <= H;++ n) {
				io.print((compress.hasZip(n) ? segment.get(Direction.LEFT).get(compress.zip(n)) : 0));
				io.print(" ");
				for (int n2 = 0;n2 < W;++ n2) io.print("  ");
				io.println((compress.hasZip(n) ? segment.get(Direction.RIGHT).get(compress.zip(n)) : 0));
			}
			io.print("*");
			for (int n = 1;n <= W;++ n) io.print(" " + (compress.hasZip(n) ? segment.get(Direction.DOWN).get(compress.zip(n)) : 0));
			io.println(" *");
			*/
		}
		long ans = 0;
		for (SegmentTree<Integer> i : segment) {
			for (int j : i.get()) ans += j;
		}
		io.println(ans);
		io.flush();
	}

	/**
	 * 端がもう片側の端と繋がり、循環する固定長配列を提供します。
	 * @author 31536000
	 *
	 * @param <T> 配列の型
	 */
	public class CircularArray<T> extends AbstractCollection<T> implements Serializable{

		private static final long serialVersionUID = 4505120414119274426L;
		final Object[] array;
		int first = 0;
		public CircularArray(int size) {
			array = new Object[size];
		}

		public CircularArray(T[] array) {
			this.array = array;
		}

		private int getIndex(int index) {
			index -= first;
			if (index >= array.length) index %= array.length;
			else if (index < 0) index = array.length + index % array.length;
			return index;
		}

		public void setFront(T value) {
			array[first] = value;
		}

		public void set(int index, T value) {
			array[getIndex(index)] = value;
		}

		public void setBack(T value) {
			array[first == 0 ? array.length - 1 : first - 1] = value;
		}

		public T get(int index) {
			@SuppressWarnings("unchecked")
			T ret = (T)array[getIndex(index)];
			return ret;
		}

		public T front() {
			@SuppressWarnings("unchecked")
			T ret = (T)array[first];
			return ret;
		}

		public T back() {
			@SuppressWarnings("unchecked")
			T ret = (T)(first == 0 ? array[array.length - 1] : array[first - 1]);
			return ret;
		}

		public void rotate(int rotate) {
			first = getIndex(rotate);
		}

		public void rotateNext() {
			if (++first >= array.length) first = 0;
		}

		public void rotatePrevious() {
			if (--first < 0) first = array.length - 1;
		}

		private class Iter implements Iterator<T> {
			private int index;
			private int count;
			Iter() {
				index = first;
				count = 0;
			}
			@Override
			public boolean hasNext() {
				return count < array.length;
			}

			@Override
			public T next() {
				@SuppressWarnings("unchecked")
				T ret = (T)array[index];
				if (++index >= array.length) index = 0;
				++ count;
				return ret;
			}
		}

		@Override
		public Iterator<T> iterator() {
			return new Iter();
		}

		@Override
		public int size() {
			return array.length;
		}
	}

	public interface SegmentTreeInterface<T, E> {
		/**
		 * データを更新します。
		 * @param dat 更新するデータ
		 * @param index 更新する場所
		 */
		public void update(E dat, int index);
		/**
		 * 区間[left, right)のデータを更新します。
		 * @param dat 更新するデータ
		 * @param left 更新する場所の左区間
		 * @param right 更新する場所の右区間
		 */
		public void update(E dat, int left, int right);
		/**
		 * 全ての値を取得します。
		 * @return 現在の値
		 */
		public T[] get();
		/**
		 * 指定した場所の値を取得します。
		 * @param index 取得したい場所
		 * @return その場所の値
		 */
		public T get(int index);
		/**
		 * 指定した範囲の合計を取得します。
		 * @param left 範囲の左区間
		 * @param right 範囲の右区間
		 * @return 半開区間[left, right)の合計
		 */
		public T get(int left, int right);
		public default int binarySearch(Predicate<T> f) {
			return binarySearch(0, size(), f);
		}
		/**
		 * 指定した範囲で二分探索を行います。
		 * @param left 範囲の左区間
		 * @param f 単調性を持つ関数
		 * @return 半開区間[left, size)において関数fがtrueを返す最大の値(無ければleft-1)
		 */
		public default int binarySearch(int left, Predicate<T> f) {
			return binarySearch(left, size(), f);
		}
		/**
		 * 指定した範囲で二分探索を行います。
		 * @param left 範囲の左区間
		 * @param right 範囲の右区間
		 * @param f 単調性を持つ関数
		 * @return 半開区間[left, right)において関数fがtrueを返す最大の値(無ければleft-1)<br>
		 * ただしleft>rightなら、半開区間[right, left)において関数fがtrueを返す最小の値(無ければleft)
		 */
		public int binarySearch(int left, int right, Predicate<T> f);
		/**
		 * 要素数を返します。
		 * @return 要素数
		 */
		public int size();
	}

	/**
	 * セグメント木です。<br>
	 * １点更新をO(logN)、範囲取得をO(logN)でできるデータ構造です。
	 * @author 31536000
	 *
	 * @param <T> 更新及び範囲取得を行いたいクラス
	 */
	public class SegmentTree<T> implements SegmentTreeInterface<T, T>{

		private Associative<T> semigroup; // 演算関数
		private T dat[]; // データ
		private int size;

		/**
		 * セグメント木を構築します。
		 * @param dat 初期値
		 * @param semigroup 演算関数
		 */
		public SegmentTree(int N, T dat, Associative<T> semigroup) {
			this.semigroup = semigroup;
			@SuppressWarnings("unchecked")
			T[] data = (T[]) new Object[N];
			Arrays.fill(data, dat);
			build(data);
		}

		/**
		 * セグメント木を構築します。
		 * @param dat 初期値
		 * @param semigroup 演算関数
		 */
		public SegmentTree(T[] dat, Associative<T> semigroup) {
			this.semigroup = semigroup;
			build(dat);
		}

		/**
		 * セグメント木を構築します。
		 * @param dat 初期値
		 * @throws ClassCastException 演算関数が定義されていなければ返す
		 */
		@SuppressWarnings("unchecked")
		public SegmentTree(int N, T dat) throws ClassCastException {
			this(N, dat, (Associative<T>) dat);
		}

		/**
		 * セグメント木を構築します。
		 * @param dat 初期値
		 * @throws ClassCastException 演算関数が定義されていなければ返す
		 */
		@SuppressWarnings("unchecked")
		public SegmentTree(T dat[]) throws ClassCastException {
			this(dat, (Associative<T>) dat[0]);
		}

		@SuppressWarnings("unchecked")
		private void build(T dat[]) { // セグ木を配列として作成
			size = dat.length;
			this.dat = (T[])new Object[Integer.highestOneBit(dat.length) << 2]; // 要素数を超える最小の2冪*2
			System.arraycopy(dat, 0, this.dat, this.dat.length >> 1, dat.length); // 最下段を埋める
			for (int i = this.dat.length / 2 - 1; i > 0; --i)
				this.dat[i] = operate(this.dat[i << 1], this.dat[i << 1 | 1]); // 最下段以外すべて、下から埋める
		}

		private T operate(T left, T right) { // 演算関数
			if (right == null) return left; // 右がnullの可能性の方がはるかに高いので
			else if (left == null) return right;
			else return semigroup.operate(left, right);
		}

		@Override
		public void update(T dat, int index) {
			index |= this.dat.length >> 1;
			this.dat[index] = dat;
			for (int i = index >> 1; i > 0; i >>= 1) this.dat[i] = operate(this.dat[i << 1], this.dat[i << 1 | 1]);
		}

		@Override
		public T[] get() {
			@SuppressWarnings("unchecked")
			T[] ret = (T[]) Array.newInstance(dat[size].getClass(), size);
			System.arraycopy(dat, dat.length >> 1, ret, 0, size);
			return  ret;
		}

		@Override
		public T get(int l, int r) {
			T L = null, R = null;
			l += dat.length >> 1;
			r += dat.length >> 1;
			while (l < r) {
				if ((l & 1) != 0) L = operate(L, dat[l++]);
				if ((r & 1) != 0) R = operate(dat[r ^ 1], R);
				l >>= 1;
				r >>= 1;
			}
			return operate(L, R);
		}

		@Override
		public T get(int index) {
			return dat[index | dat.length >> 1];
		}

		@Override
		public int size() {
			return size;
		}

		@Override
		public void update(T dat, int left, int right) {
			for (int i = left;i < right;++ i) update(dat, i);
		}

		private int revBinarySearch(int right, int left, Predicate<T> f) {
			left += dat.length >>> 1;
			right += dat.length >>> 1;
			T last = null, next;
			int i = 0;
			while (left >>> i < right) {
				if ((right & 1) == 0) { // 上がある
					if (f.test(next = operate(dat[right], last))) { // このright全部を含むか
						last = next;
						-- right;
					} else left = right << i; // 左辺を移動
				} else {
					right >>>= 1;
					++ i;
				}
			}
			while (i > 0) { // 今度は降下しながら見ていく
				right = right << 1 | 1;
				-- i;
				if ((left >>> i & 1) == 0) {
					if (f.test(next = operate( dat[right], last))) {
						last = next;
						-- right;
					} else left = right << i;
				}
			};
			return right - (dat.length >>> 1) + 1;
		}

		@Override
		public int binarySearch(int left, int right, Predicate<T> f) {
			if (left > right) return revBinarySearch(left - 1, right - 1, f);
			left += dat.length >>> 1;
			right += dat.length >>> 1;
			T last = null, next;
			int i = 0;
			while (left < right >>> i) {
				if ((left & 1) == 0) { // 上がある
					left >>>= 1;
					++ i;
				} else {
					if (f.test(next = operate(last, dat[left]))) { // このleft全部を含むか
						last = next;
						++ left;
					} else right = (left + 1 << i) - 1; // 左辺を移動
				}
			}
			while (i > 0) { // 今度は降下しながら見ていく
				left <<= 1;
				-- i;
				if ((right >>> i & 1) != 0) {
					if (f.test(next = operate(last, dat[left]))) {
						last = next;
						++ left;
					} else right = (left + 1 << i) - 1;
				}
			};
			return left - (dat.length >>> 1) - 1;
		}
	}

	public interface Associative<T> {
		public T operate(T left, T right);
	}

	/**
	 * 座標圧縮をするライブラリです。
	 * @author 31536000
	 *
	 * @param <T> 座標圧縮を行う型
	 */
	public class CompressTree<T extends Comparable<T>>{
		private TreeMap<T, Integer> zip;
		private Object[] unzip;

		/**
		 * datを用いて座圧します。
		 * @param dat 座圧する値
		 */
		public CompressTree(T[] dat) {
			Arrays.sort(dat);
			zip = new TreeMap<T, Integer>();
			List<T> unzip = new ArrayList<T>();
			for (int i = 0, j = 0;i < dat.length;++ i) {
				if (zip.put(dat[i], j++) != null) {
					zip.put(dat[i], --j-1);
				} else unzip.add(dat[i]);
			}
			this.unzip = unzip.toArray();
		}

		/**
		 * datを用いて座圧します。
		 * @param dat 座圧する値
		 */
		public CompressTree(List<T> dat) {
			dat.sort(null);
			Object[] dats = dat.toArray();
			zip = new TreeMap<T, Integer>();
			List<T> unzip = new ArrayList<T>();
			for (int i = 0, j = 0;i < dats.length;++ i) {
				@SuppressWarnings("unchecked")
				T push = (T) dats[i];
				if (zip.put(push, j++) != null) {
					zip.put(push, --j-1);
				} else unzip.add(push);
			}
			this.unzip = unzip.toArray();
		}

		public boolean hasZip(T dat) {
			return zip.containsKey(dat);
		}

		/**
		 * 座圧した値を求めます。
		 * @param dat 座圧前の値
		 * @return 座圧後の値
		 */
		public int zip(T dat) {
			return zip.get(dat);
		}

		/**
		 * 座圧した値を求めます。
		 * @param dat 座圧前の値
		 * @return 座圧後の値
		 */
		public int floorZip(T dat) {
			return zip.floorEntry(dat).getValue();
		}

		/**
		 * 座圧した値を求めます。
		 * @param dat 座圧前の値
		 * @return 座圧後の値
		 */
		public int ceilingZip(T dat) {
			return zip.ceilingEntry(dat).getValue();
		}

		/**
		 * 座圧前の値を求めます。
		 * @param index 座圧後の値
		 * @return 座圧前の値
		 */
		public T unzip(int index) {
			@SuppressWarnings("unchecked")
			T ret = (T)unzip[index];
			return ret;
		}

		/**
		 * 要素数を求めます。
		 * @return ユニークな要素数
		 */
		public int size() {
			return unzip.length;
		}
	}

	public class FastIO {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int read = 0;
		private int length = 0;
		public final PrintWriter out = new PrintWriter(System.out, false);
		public final PrintWriter err = new PrintWriter(System.err, false);

		private boolean hasNextByte() {
			if (read < length) return true;
			read = 0;
			try {
				length = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			return length > 0;
		}

		private int readByte() {
			return hasNextByte() ? buffer[read++] : -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		private boolean isNumber(int c) {
			return '0' <= c && c <= '9';
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[read])) read++;
			return hasNextByte();
		}

		public char nextChar() {
			if (!hasNextByte())  throw new NoSuchElementException();
			return (char)readByte();
		}

		public char[][] nextChar(int height) {
			char[][] ret = new char[height][];
			for (int i = 0;i < ret.length;++ i) ret[i] = next().toCharArray();
			return ret;
		}

		public String next() {
			if (!hasNext()) throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b;
			while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext()) throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (!isNumber(b)) throw new NumberFormatException();
			while (true) {
				if (isNumber(b)) {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n;
				else throw new NumberFormatException();
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextInt(int width) {
			int[] ret = new int[width];
			for (int i = 0;i < width;++ i) ret[i] = nextInt();
			return ret;
		}

		public long[] nextLong(int width) {
			long[] ret = new long[width];
			for (int i = 0;i < width;++ i) ret[i] = nextLong();
			return ret;
		}

		public int[][] nextInt(int width, int height) {
			int[][] ret = new int[height][width];
			for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[i][j] = nextInt();
			return ret;
		}

		public long[][] nextLong(int width, int height) {
			long[][] ret = new long[height][width];
			for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
			return ret;
		}

		public boolean[] nextBoolean(char T) {
			char[] s = next().toCharArray();
			boolean[] ret = new boolean[s.length];
			for (int i = 0;i < ret.length;++ i) ret[i] = s[i] == T;
			return ret;
		}

		public boolean[][] nextBoolean(char T, int height) {
			boolean[][] ret = new boolean[height][];
			for (int i = 0;i < ret.length;++ i) {
				char[] s = next().toCharArray();
				ret[i] = new boolean[s.length];
				for (int j = 0;j < ret[i].length;++ j) ret[i][j] = s[j] == T;
			}
			return ret;
		}

		public Point nextPoint() {
			return new Point(nextInt(), nextInt());
		}

		public Point[] nextPoint(int width) {
			Point[] ret = new Point[width];
			for (int i = 0;i < width;++ i) ret[i] = nextPoint();
			return ret;
		}

		@Override
		protected void finalize() throws Throwable {
			try {
				super.finalize();
			} finally {
				in.close();
				out.close();
				err.close();
			}
		}

		public void print(boolean b) {
			out.print(b);
		}

		public void print(char c) {
			out.print(c);
		}

		public void print(char[] s) {
			out.print(s);
		}

		public void print(double d) {
			out.print(d);
		}

		public void print(double d, int length) {
			if (d < 0) {
				out.print('-');
				d = -d;
			}
			d += Math.pow(10, -length) / 2;
			out.print((long)d);
			out.print('.');
			d -= (long)d;
			for (int i = 0;i < length;++ i) {
				d *= 10;
				out.print((int)d);
				d -= (int)d;
			}
		}

		public void print(float f) {
			out.print(f);
		}

		public void print(int i) {
			out.print(i);
		}

		public void print(long l) {
			out.print(l);
		}

		public void print(Object obj) {
			out.print(obj);
		}

		public void print(String s) {
			out.print(s);
		}

		public void print(Object[] obj, String perse) {
			print(obj[0]);
			for (int i = 1;i < obj.length;++ i) {
				print(perse);
				print(obj[i]);
			}
		}

		public void print(Object[][] obj, String perse1, String perse2) {
			print(obj[0], perse1);
			for (int i = 1;i < obj.length;++ i) {
				print(perse2);
				print(obj[i], perse1);
			}
		}

		public void printf(String format, Object... args) {
			out.printf(format, args);
		}

		public void printf(Locale l, String format, Object... args) {
			out.printf(l, format, args);
		}

		public void println() {
			out.println();
		}

		public void println(boolean b) {
			out.println(b);
		}

		public void println(char c) {
			out.println(c);
		}

		public void println(char[] s) {
			out.println(s);
		}

		public void println(double d) {
			out.println(d);
		}

		public void println(double d, int length) {
			print(d, length);
			println();
		}

		public void println(float f) {
			out.println(f);
		}

		public void println(int i) {
			out.println(i);
		}

		public void println(long l) {
			out.println(l);
		}

		public void println(Object obj) {
			out.println(obj);
		}

		public void println(String s) {
			out.println(s);
		}

		public void println(Object[] obj, String perse) {
			print(obj, perse);
			println();
		}

		public void println(Object[][] obj, String perse1, String perse2) {
			print(obj, perse1, perse2);
			println();
		}

		public void flush() {
			out.flush();
			err.flush();
		}
	}

	public enum BoundType {
		CLOSED, OPEN;
	}

	public static class Range<C> implements Serializable{

		private static final long serialVersionUID = -4702828934863023392L;
		protected C lower;
		protected C upper;
		protected BoundType lowerType;
		protected BoundType upperType;
		private Comparator<? super C> comparator;

		protected Range(C lower, BoundType lowerType, C upper, BoundType upperType) {
			this(lower, lowerType, upper, upperType, null);
		}

		protected Range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
			this.lower = lower;
			this.upper = upper;
			this.lowerType = lowerType;
			this.upperType = upperType;
			this.comparator = comparator;
		}

		public static <C extends Comparable<? super C>> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType) {
			if (lower != null && upper != null) {
				int comp = lower.compareTo(upper);
				if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
				else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN))return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
			}
			return new Range<C>(lower, lowerType, upper, upperType);
		}

		public static <C> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
			if (lower != null && upper != null) {
				int comp = comparator.compare(lower, upper);
				if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
				else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
			}
			return new Range<C>(lower, lowerType, upper, upperType, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> all() {
			return range(null, BoundType.OPEN, null, BoundType.OPEN);
		}

		public static <C> Range<C> all(Comparator<? super C> comparator) {
			return range(null, BoundType.OPEN, null, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> atMost(C upper) {
			return range(null, BoundType.OPEN, upper, BoundType.CLOSED);
		}

		public static <C> Range<C> atMost(C upper, Comparator<? super C> comparator) {
			return range(null, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> lessThan(C upper) {
			return range(null, BoundType.OPEN, upper, BoundType.OPEN);
		}

		public static <C> Range<C> lessThan(C upper, Comparator<? super C> comparator) {
			return range(null, BoundType.OPEN, upper, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> downTo(C upper, BoundType boundType) {
			return range(null, BoundType.OPEN, upper, boundType);
		}

		public static <C> Range<C> downTo(C upper, BoundType boundType, Comparator<? super C> comparator) {
			return range(null, BoundType.OPEN, upper, boundType, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> atLeast(C lower) {
			return range(lower, BoundType.CLOSED, null, BoundType.OPEN);
		}

		public static <C> Range<C> atLeast(C lower, Comparator<? super C> comparator) {
			return range(lower, BoundType.CLOSED, null, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> greaterThan(C lower) {
			return range(lower, BoundType.OPEN, null, BoundType.OPEN);
		}

		public static <C> Range<C> greaterThan(C lower, Comparator<? super C> comparator) {
			return range(lower, BoundType.OPEN, null, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> upTo(C lower, BoundType boundType) {
			return range(lower, boundType, null, BoundType.OPEN);
		}

		public static <C> Range<C> upTo(C lower, BoundType boundType, Comparator<? super C> comparator) {
			return range(lower, boundType, null, BoundType.OPEN, comparator  );
		}

		public static <C extends Comparable<? super C>> Range<C> open(C lower, C upper) {
			return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
		}

		public static <C> Range<C> open(C lower, C upper, Comparator<? super C> comparator) {
			return range(lower, BoundType.OPEN, upper, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> openClosed(C lower, C upper) {
			return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
		}

		public static <C> Range<C> openClosed(C lower, C upper, Comparator<? super C> comparator) {
			return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> closedOpen(C lower, C upper) {
			return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
		}

		public static <C> Range<C> closedOpen(C lower, C upper, Comparator<? super C> comparator) {
			return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> closed(C lower, C upper) {
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
		}

		public static <C> Range<C> closed(C lower, C upper, Comparator<? super C> comparator) {
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> singleton(C value) {
			return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
		}

		public static <C> Range<C> singleton(C value, Comparator<? super C> comparator) {
			return range(value, BoundType.CLOSED, value, BoundType.CLOSED, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> empty() {
			return range(null, BoundType.CLOSED, null, BoundType.CLOSED);
		}

		public static <C> Range<C> empty(Comparator<? super C> comparator) {
			return range(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
		}

		public static <C extends Comparable<? super C>> Range<C> encloseAll(Iterable<C> values) {
			C lower = values.iterator().next();
			C upper = lower;
			for (C i : values) {
				if (lower.compareTo(i) > 0) lower = i;
				if (upper.compareTo(i) < 0) upper = i;
			}
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
		}

		public static <C> Range<C> encloseAll(Iterable<C> values, Comparator<? super C> comparator) {
			C lower = values.iterator().next();
			C upper = lower;
			for (C i : values) {
				if (comparator.compare(lower, i) > 0) lower = i;
				if (comparator.compare(upper, i) < 0) upper = i;
			}
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
		}

		protected int compareLower(C value) {
			return compareLower(value, BoundType.CLOSED);
		}

		protected int compareLower(C value, BoundType boundType) {
			return compareLower(lower, lowerType, value, boundType);
		}

		protected int compareLower(C lower, BoundType lowerType, C value) {
			return compareLower(lower, lowerType, value, BoundType.CLOSED);
		}

		protected int compareLower(C lower, BoundType lowerType, C value, BoundType boundType) {
			if (lower == null) return value == null ? 0 : -1;
			else if (value == null) return 1;
			int compare;
			if (comparator == null) {
				@SuppressWarnings("unchecked")
				Comparable<C> comp = (Comparable<C>)lower;
				compare = comp.compareTo(value);
			} else compare = comparator.compare(lower, value);
			if (compare == 0) {
				if (lowerType == BoundType.CLOSED) -- compare;
				if (boundType == BoundType.CLOSED) ++ compare;
			}
			return compare;
		}

		protected int compareUpper(C value) {
			return compareUpper(value, BoundType.CLOSED);
		}

		protected int compareUpper(C value, BoundType boundType) {
			return compareUpper(upper, upperType, value, boundType);
		}

		protected int compareUpper(C upper, BoundType upperType, C value) {
			return compareUpper(upper, upperType, value, BoundType.CLOSED);
		}

		protected int compareUpper(C upper, BoundType upperType, C value, BoundType boundType) {
			if (upper == null) return value == null ? 0 : 1;
			if (value == null) return -1;
			int compare;
			if (comparator == null) {
				@SuppressWarnings("unchecked")
				Comparable<C> comp = (Comparable<C>)upper;
				compare = comp.compareTo(value);
			} else compare = comparator.compare(upper, value);
			if (compare == 0) {
				if (upperType == BoundType.CLOSED) ++ compare;
				if (boundType == BoundType.CLOSED) -- compare;
			}
			return compare;
		}

		public boolean hasLowerBound() {
			return lower != null;
		}

		public C lowerEndpoint() {
			if (hasLowerBound()) return lower;
			throw new IllegalStateException();
		}

		public BoundType lowerBoundType() {
			if (hasLowerBound()) return lowerType;
			throw new IllegalStateException();
		}

		public boolean hasUpperBound() {
			return upper != null;
		}

		public C upperEndpoint() {
			if (hasUpperBound()) return upper;
			throw new IllegalStateException();
		}

		public BoundType upperBoundType() {
			if (hasUpperBound()) return upperType;
			throw new IllegalStateException();
		}

		/**
		 * この区間が空集合か判定します。
		 * @return 空集合ならばtrue
		 */
		public boolean isEmpty() {
			return lower == null && upper == null && lowerType == BoundType.CLOSED;
		}

		/**
		 * 与えられた引数が区間の左側に位置するか判定します。<br>
		 * 接する場合は区間の左側ではないと判定します。
		 * @param value 調べる引数
		 * @return 区間の左側に位置するならtrue
		 */
		public boolean isLess(C value) {
			return isLess(value, BoundType.CLOSED);
		}

		protected boolean isLess(C value, BoundType boundType) {
			return compareLower(value, boundType) > 0;
		}

		/**
		 * 与えられた引数が区間の右側に位置するか判定します。<br>
		 * 接する場合は区間の右側ではないと判定します。
		 * @param value 調べる引数
		 * @return 区間の右側に位置するならtrue
		 */
		public boolean isGreater(C value) {
			return isGreater(value, BoundType.CLOSED);
		}

		private boolean isGreater(C value, BoundType boundType) {
			return compareUpper(value, boundType) < 0;
		}

		/**
		 * 与えられた引数が区間内に位置するか判定します。<br>
		 * 接する場合も区間内に位置すると判定します。
		 * @param value 調べる引数
		 * @return 区間内に位置するならtrue
		 */
		public boolean contains(C value) {
			return !isLess(value) && !isGreater(value) && !isEmpty();
		}

		/**
		 * 与えられた引数すべてが区間内に位置するか判定します。<br>
		 * 接する場合も区間内に位置すると判定します。
		 * @param value 調べる要素
		 * @return 全ての要素が区間内に位置するならtrue
		 */
		public boolean containsAll(Iterable<? extends C> values) {
			for (C i : values) if (!contains(i)) return false;
			return true;
		}

		/**
		 * 与えられた区間がこの区間に内包されるか判定します。<br>
		 *
		 * @param other
		 * @return 与えられた区間がこの区間に内包されるならtrue
		 */
		public boolean encloses(Range<C> other) {
			return !isLess(other.lower, other.lowerType) && !isGreater(other.upper, other.upperType);
		}

		/**
		 * 与えられた区間がこの区間と公差するか判定します。<br>
		 * 接する場合は公差するものとします。
		 * @param value 調べる引数
		 * @return 区間が交差するならtrue
		 */
		public boolean isConnected(Range<C> other) {
			if (this.isEmpty() || other.isEmpty()) return false;
			C lower, upper;
			BoundType lowerType, upperType;
			if (isLess(other.lower, other.lowerType)) {
				lower = other.lower;
				lowerType = other.lowerType;
			} else {
				lower = this.lower;
				lowerType = this.lowerType;
			}
			if (isGreater(other.upper, other.upperType)) {
				upper = other.upper;
				upperType = other.upperType;
			} else {
				upper = this.upper;
				upperType = this.upperType;
			}
			if (lower == null || upper == null) return true;
			int comp = compareLower(lower, lowerType, upper, upperType);
			return comp <= 0;
		}
		/**
		 * この区間との積集合を返します。
		 * @param connectedRange 積集合を求める区間
		 * @return 積集合
		 */
		public Range<C> intersection(Range<C> connectedRange) {
			if (this.isEmpty() || connectedRange.isEmpty()) {
				if (comparator == null) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
				return empty(comparator);
			}
			C lower, upper;
			BoundType lowerType, upperType;
			if (isLess(connectedRange.lower, connectedRange.lowerType)) {
				lower = connectedRange.lower;
				lowerType = connectedRange.lowerType;
			} else {
				lower = this.lower;
				lowerType = this.lowerType;
			}
			if (isGreater(connectedRange.upper, connectedRange.upperType)) {
				upper = connectedRange.upper;
				upperType = connectedRange.upperType;
			} else {
				upper = this.upper;
				upperType = this.upperType;
			}
			if (comparator == null) {
				return new Range<C>(lower, lowerType, upper, upperType);
			}
			return range(lower, lowerType, upper, upperType, comparator);
		}

		/**
		 * この区間との和集合を返します。
		 * @param other 和集合を求める区間
		 * @return 和集合
		 */
		public Range<C> span(Range<C> other) {
			if (other.isEmpty()) return new Range<C>(lower, lowerType, upper, upperType);
			C lower, upper;
			BoundType lowerType, upperType;
			if (isLess(other.lower, other.lowerType)) {
				lower = this.lower;
				lowerType = this.lowerType;
			} else {
				lower = other.lower;
				lowerType = other.lowerType;
			}
			if (isGreater(other.upper, other.upperType)) {
				upper = this.upper;
				upperType = this.upperType;
			} else {
				upper = other.upper;
				upperType = other.upperType;
			}
			return new Range<C>(lower, lowerType, upper, upperType, comparator);
		}

		@Override
		public boolean equals(Object object) {
			if (this == object) return true;
			if (object instanceof Range) {
				@SuppressWarnings("unchecked")
				Range<C> comp = (Range<C>) object;
				return compareLower(comp.lower, comp.lowerType) == 0 && compareUpper(comp.upper, comp.upperType) == 0 && lowerType == comp.lowerType && upperType == comp.upperType;
			}
			return false;
		}

		@Override
		public int hashCode() {
			if (lower == null && upper == null) return 0;
			else if (lower == null) return upper.hashCode();
			else if (upper == null) return lower.hashCode();
			return lower.hashCode() ^ upper.hashCode();
		}

		@Override
		public String toString() {
			if (isEmpty()) return "()";
			return (lowerType == BoundType.OPEN ? "(" : "[") + (lower == null ? "" : lower.toString()) + ".." + (upper == null ? "" : upper.toString()) + (upperType == BoundType.OPEN ? ")" : "]");
		}
	}

	public interface IterableFunction<T> {
		public T next(T value);
	}

	public static class IterableRange<C> extends Range<C> implements Iterable<C>{

		private static final long serialVersionUID = 9065915259748260688L;
		protected IterableFunction<C> func;

		protected IterableRange(C lower, BoundType lowerType, C upper, BoundType upperType, IterableFunction<C> func) {
			super(lower, lowerType, upper, upperType);
			this.func = func;
		}

		public static <C extends Comparable<? super C>> IterableRange<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, IterableFunction<C> func) {
			if (lower == null || upper == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
			int comp = lower.compareTo(upper);
			if (comp > 0) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
			else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
			return new IterableRange<C>(lower, lowerType, upper, upperType, func);
		}

		public static <C extends Comparable<? super C>> IterableRange<C> open(C lower, C upper, IterableFunction<C> func) {
			if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
			return range(func.next(lower), BoundType.CLOSED, upper, BoundType.OPEN, func);
		}

		public static <C extends Comparable<? super C>> IterableRange<C> openClosed(C lower, C upper, IterableFunction<C> func) {
			if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
			return range(func.next(lower), BoundType.CLOSED, upper, BoundType.CLOSED, func);
		}

		public static <C extends Comparable<? super C>> IterableRange<C> closedOpen(C lower, C upper, IterableFunction<C> func) {
			return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func);
		}

		public static <C extends Comparable<? super C>> IterableRange<C> closed(C lower, C upper, IterableFunction<C> func) {
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
		}

		public static <C extends Comparable<? super C>> IterableRange<C> singleton(C value, IterableFunction<C> func) {
			return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func);
		}
		private class Iter implements Iterator<C> {
			C now;
			Iter() {
				now = lower;
			}
			@Override
			public final boolean hasNext() {
				return !isGreater(now);
			}

			@Override
			public final C next() {
				C ret = now;
				now = func.next(now);
				return ret;
			}

			@Override
			public final void remove() {
				throw new UnsupportedOperationException();
			}
		}

		@Override
		public Iterator<C> iterator() {
			return new Iter();
		}

		public int getDistance() {
			C check = upper;
			int ret = 0;
			while (lower != check) {
				check = func.next(check);
				++ ret;
			}
			return ret;
		}
	}

	public static class IntRange extends IterableRange<Integer>{

		private static final long serialVersionUID = 8177932312110314067L;

		private static class Next implements IterableFunction<Integer> {

			@Override
			public Integer next(Integer value) {
				return value + 1;
			}
		}

		protected IntRange() {
			super(null, BoundType.CLOSED, null, BoundType.CLOSED, new Next());
		}

		protected IntRange(int lower, BoundType lowerType, int upper, BoundType upperType) {
			super(lower, lowerType, upper, upperType, new Next());
		}

		public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType) {
			if (lower > upper) return new IntRange();
			if (lowerType == BoundType.OPEN) ++ lower;
			if (upperType == BoundType.OPEN) -- upper;
			return new IntRange(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
		}

		public static IntRange open(int lower, int upper) {
			return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
		}

		public static IntRange open(int upper) {
			return range(0, BoundType.CLOSED, upper, BoundType.OPEN);
		}

		public static IntRange openClosed(int lower, int upper) {
			return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
		}

		public static IntRange closedOpen(int lower, int upper) {
			return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
		}

		public static IntRange closed(int lower, int upper) {
			return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
		}

		public static IntRange closed(int upper) {
			return range(0, BoundType.CLOSED, upper, BoundType.CLOSED);
		}

		public static IntRange singleton(int value) {
			return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
		}

		private class Iter implements Iterator<Integer> {
			int now;
			public Iter() {
				now = lower;
			}
			@Override
			public final boolean hasNext() {
				return now <= upper;
			}

			@Override
			public final Integer next() {
				return now++;
			}

			@Override
			public final void remove() {
				throw new UnsupportedOperationException();
			}
		}

		@Override
		public Iterator<Integer> iterator() {
			return new Iter();
		}

		@Override
		public int getDistance() {
			int ret = upper - lower;
			if (upperType == BoundType.CLOSED) ++ ret;
			return ret;
		}

		public int getClosedLower() {
			return lower;
		}

		public int getOpenLower() {
			return lower - 1;
		}

		public int getClosedUpper() {
			return upperType == BoundType.CLOSED ? upper : upper - 1;
		}

		public int getOpenUpper() {
			return upperType == BoundType.CLOSED ? upper + 1 : upper;
		}
	}
}