import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;

class Util {
	public static IllegalArgumentException BadArgf(String fmt, Object... args) {
		return new IllegalArgumentException(String.format(fmt, args));
	};

	public static String trace(Exception e) {
		StringWriter sw = new StringWriter();
		e.printStackTrace(new PrintWriter(sw));
		return sw.toString();
	}

	public static int rangecheck(int x, int min, int max, String what) {
		if (x < min || x > max) throw BadArgf("Bad %s: %d, should be [%d; %d].", what, x, min, max);
		return x;
	}
}

class Bitfield2D {
	int[] data;
	int w, h;
	static final int SANE_BITS_LIMIT = 1_000_000_000;
	static final int SANE_DIMENSION_LIMIT = 100_000_000;
	static final int BASE = Integer.SIZE; 
	// BASE expected to be power of 2, then
	// (bitno >> BASEP2) is faster version of (bitno / BASE), and
	// (bitno & BASEMASK) is faster version of (bitno % BASE).
	//
	// Compiler cannot optimize these operations as effectively as programmer can,
	// because they work differently for negative 'bitno' values, so it should check for negatives.
	// And it's only we who know that 'bitno' is never negative.
	//
	// Not sure if there is no danger of BASEP2 formula NOT resulting in compile-time constant,
	// but it appears to be OK.
	static final int BASEP2 = 32 - (Integer.numberOfLeadingZeros(BASE) + 1);
	static final int BASEMASK = BASE - 1;

	public Bitfield2D(int w, int h) {
		validateSize(w, h);
		this.data = new int[(w*h + (BASE - 1)) >> BASEP2];
		this.w = w;
		this.h = h;
	}

	static void validateSize(int w, int h) {
		if (w < 0 || h < 0 || w > SANE_DIMENSION_LIMIT || h > SANE_DIMENSION_LIMIT
			|| w > 0 && h > SANE_BITS_LIMIT / w)
			throw Util.BadArgf("Bad bitfield size: %d×%d.", w, h);
	}

	public static boolean validCoord(int w, int h, int x, int y) {
		return x >= 0 && y >= 0 && x < w && y < h;
	}

	public static void validateCoord(int w, int h, int x, int y) {
		if (!validCoord(w, h, x, y))
			throw Util.BadArgf("Bad coord of bitfield %d×%d: (%d, %d).", w, h, x, y);
	}

	static void validateRect(int fullw, int fullh, int x, int y, int w, int h) {
		if (x < 0 || y < 0 || w < 0 || h < 0 || x + w > fullw || y + h > fullh)
			throw Util.BadArgf("Bad rect of bitfield %d×%d: (%d, %d) ~ (%d, %d).",
				fullw, fullh, x, y, x+w, y+h);
	}

	boolean rawget(int index) { return (data[index >> BASEP2] & (1 << (index & BASEMASK))) != 0; }
	void rawset(int index) { data[index >> BASEP2] |= 1 << (index & BASEMASK); }
	void rawunset(int index) { data[index >> BASEP2] &= ~(1 << (index & BASEMASK)); }
	void rawset(int index, boolean value) { if (value) rawset(index); else rawunset(index); }

	public boolean get(int x, int y) { validateCoord(w, h, x, y); return rawget(y*w+x); }
	public void set(int x, int y) { validateCoord(w, h, x, y); rawset(y*w+x); }
	public void unset(int x, int y) { validateCoord(w, h, x, y); rawunset(y*w+x); }
	public void set(int x, int y, boolean value) { validateCoord(w, h, x, y); rawset(y*w+x, value); }
	public int width() { return w; }
	public int height() { return h; }

	// For functions like or() that apply one bitfield to another,
	// reduces potentially out-of-borders input to its valid part.
	static class CoordWarden {
		int srcX, srcY, w, h, destX, destY;

		CoordWarden(int destFullW, int destFullH, int srcFullW, int srcFullH,
			int aSrcX, int aSrcY, int aW, int aH, int aDestX, int aDestY) {

			validateRect(srcFullW, srcFullH, aSrcX, aSrcY, aW, aH);
			srcX = aSrcX; srcY = aSrcY; w = aW; h = aH; destX = aDestX; destY = aDestY;
			if (destX < 0) { srcX -= destX; w += destX; destX = 0; }
			if (destX + w > destFullW) { w = destFullW - destX; }
			if (destY < 0) { srcY -= destY; h += destY; destY = 0; }
			if (destY + h > destFullH) { h = destFullH - destY; }
		}
	}

	public void or(Bitfield2D b, int thisX, int thisY) {
		or(b, 0, 0, b.w, b.h, thisX, thisY);
	}

	public void or(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w)
			for (int dx = 0; dx < ward.w; dx++, thisOfs++, bOfs++)
				if (b.rawget(bOfs)) this.rawset(thisOfs);
	}

	public void orBATCH(Bitfield2D b, int thisX, int thisY) {
		orBATCH(b, 0, 0, b.w, b.h, thisX, thisY);
	}

	public void orBATCH(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
		apply(b, bx, by, w, h, thisX, thisY, (itemA, itemB) -> itemA | itemB);
	}

	public void andNot(Bitfield2D b, int thisX, int thisY) {
		andNot(b, 0, 0, b.w, b.h, thisX, thisY);
	}

	public void andNot(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w)
			for (int dx = 0; dx < ward.w; dx++, thisOfs++, bOfs++)
				if (b.rawget(bOfs)) this.rawunset(thisOfs);
	}

	public void andNotBATCH(Bitfield2D b, int thisX, int thisY) {
		andNotBATCH(b, 0, 0, b.w, b.h, thisX, thisY);
	}

	public void andNotBATCH(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
		apply(b, bx, by, w, h, thisX, thisY, (itemA, itemB) -> itemA & ~itemB);
	}

	@FunctionalInterface
	interface Operation {
		abstract int apply(int a, int b);
	}

	void apply(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY, Operation op) {
		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w, bOfs += b.w)
			applyOp(this.data, thisOfs, b.data, bOfs, ward.w, op);
	}

	public Bitfield2D copyFrom(Bitfield2D b, int thisX, int thisY) {
		return copyFrom(b, 0, 0, b.w, b.h, thisX, thisY);
	}

	public Bitfield2D copyFrom(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w, bOfs += b.w)
			copyBits(b.data, bOfs, this.data, thisOfs, ward.w);
		return this;
	}

	static int readBitsSmall(int[] src, int srcPos, int count) {
		assert count > 0 && count < BASE;
		//       0       1       2       3       4       5       6
		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
		//            ^srcPos=5
		//                  ^srcPos+count=11
		int bits = src[srcPos >> BASEP2] >>> (srcPos & BASEMASK); // FGH
		if (count > BASE - (srcPos & BASEMASK))
			bits |= src[(srcPos >> BASEP2) + 1] << (BASE - (srcPos & BASEMASK)); // FGH | 000IJKLMNOP = FGHIJKLMNOP
		return bits & ((1 << count) - 1); // FGHIJK
	}

	static void writeBits1(int bits, int[] dst, int dstPos, int count) {
		assert count > 0 && count < BASE - (dstPos & BASEMASK) && bits < 1 << count;
		// bits = qwer
		//       0       1       2       3       4       5       6
		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
		//          ^dstPos=3
		//              ^dstPos+count=7
		dst[dstPos >> BASEP2] = dst[dstPos >> BASEP2] // ABCDEFGH
			& ~(((1 << count) - 1) << (dstPos & BASEMASK)) // ABC0000H
			| (bits << (dstPos & BASEMASK)); // ABCqwerH
	}

	static void copyBits(int[] src, int srcPos, int[] dst, int dstPos, int count) {
		// Imagine BASE=8 (as if byte[] instead of int[]), srcPos = 3, dstPos = 2, count=25.
		//
		//       0       1       2       3       4       5       6
		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
		//          ^srcPos=3                ^srcPos+count=28
		// dst = ...............................................
		//       0 ^dstPos=2     2       3       4       5
		//
		// First we align dstPos to the multiple of BASE by reading
		// first BASE - dstPos%BASE bits with readBitsSmall() and writing them
		// into the first cell of dst[] with writeBits1.
		//
		// We'll get:
		//       0       1       2       3       4       5       6
		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
		//                ^srcPos=9          ^srcPos+count=28
		// dst = ..DEFGHI.......................................
		//       0       1       2       3       4       5
		//               ^dstPos=8
		if ((dstPos & BASEMASK) != 0) {
			int n = min(count, BASE - (dstPos & BASEMASK));
			if (n > 0) writeBits1(readBitsSmall(src, srcPos, n), dst, dstPos, n);
			srcPos += n;
			dstPos += n;
			count -= n;
		}

		// Now we fill whole cells while possible.
		// We'll get:
		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
		//                                ^srcPos=25
		//                                   ^srcPos+count=28
		// dst = ..DEFGHIJKLMNOPQRSTUVWXY.......................
		//       0       1       2       3       4       5
		//                               ^dstPos=24
		if (count >= BASE) {
			if ((srcPos & BASEMASK) == 0) {
				// Aligned case. This is not even an optimization, because 'int' shifts are restricted to 0..31.
				System.arraycopy(src, srcPos >> BASEP2, dst, dstPos >> BASEP2, count >> BASEP2);
			} else {
				// Unaligned case.
				// src: ...ABCDE FGH.....
				//         ^srcPos
				// dst: ........
				for (int iSrc = srcPos >> BASEP2, iDst = dstPos >> BASEP2, iDstEd = iDst + (count >> BASEP2); iDst < iDstEd; iDst++, iSrc++)
					dst[iDst] =
						(src[iSrc] >>> (srcPos & BASEMASK)) // ABCDE
						| (src[iSrc + 1] << (BASE - (srcPos & BASEMASK))); // ABCDE | 00000FGH = ABCDEFGH
			}
			srcPos += count - (count & BASEMASK);
			dstPos += count - (count & BASEMASK);
			count &= BASEMASK;
		}

		// Append the tail.
		if (count > 0)
			writeBits1(readBitsSmall(src, srcPos, count), dst, dstPos, count);
	}

	// Same as copyBits() but with custom operation instead of copying.
	// Argument order changed both to emphasize modifying 'dst' and
	// to match the order in op.apply: (dst, src) that matters for noncommutative operations.
	// Speaking of it, the only reason why copyBits() has (src, srcPos, dst,
	// dstPos, count) order is consistency with System.arraycopy.
	static void applyOp(int[] dst, int dstPos, int[] src, int srcPos, int count, Operation op) {
		if ((dstPos & BASEMASK) != 0) {
			int n = min(count, BASE - (dstPos & BASEMASK));
			if (n > 0) writeBits1(op.apply(readBitsSmall(dst, dstPos, n), readBitsSmall(src, srcPos, n)), dst, dstPos, n);
			srcPos += n; dstPos += n; count -= n;
		}
		if (count >= BASE) {
			for (int iSrc = srcPos >> BASEP2, iDst = dstPos >> BASEP2, iDstEd = iDst + (count >> BASEP2); iDst < iDstEd; iDst++, iSrc++)
				dst[iDst] = op.apply(dst[iDst], (srcPos & BASEMASK) == 0 ? src[iSrc] : (src[iSrc] >>> (srcPos & BASEMASK)) | (src[iSrc + 1] << (BASE - (srcPos & BASEMASK))));
			srcPos += count - (count & BASEMASK); dstPos += count - (count & BASEMASK); count &= BASEMASK;
		}
		if (count > 0)
			writeBits1(op.apply(readBitsSmall(dst, dstPos, count), readBitsSmall(src, srcPos, count)), dst, dstPos, count);
	}

	@Override
	public String toString() {
		return toString("##", "..");
	}

	public String toString(String one, String zero) {
		var sb = new StringBuilder();
		for (int ofs = 0, y = 0; y < h; y++) {
			if (y > 0) sb.append("\n");
			for (int x = 0; x < w; x++, ofs++)
				sb.append(rawget(ofs) ? one : zero);
		}
		return sb.toString();
	}

	static Bitfield2D parse(String src) { return parse(src, "##"); }

	static Bitfield2D parse(String src, String one) {
		if (one.isEmpty()) throw Util.BadArgf("'one' can't be empty.");
		if (one.indexOf('\n') >= 0) throw Util.BadArgf("Bad 'one': \"%s\". Shouldn't contain EOL.", one);
		// Prepass for size.
		int w = 0, h = 0;
		for (int pos = 0; pos < src.length(); ) {
			int eolp = src.indexOf("\n", pos);
			if (eolp < 0) eolp = src.length();
			if ((eolp - pos) % one.length() != 0)
				throw Util.BadArgf("Line %d:\n%s\ncontains %d character%s, which is not multiple of len(%s) = %d.",
					h, src.substring(pos, eolp), eolp - pos, eolp - pos != 1 ? "s" : "", one, one.length());
			w = max(w, (eolp - pos) / one.length());
			h++;
			pos = eolp + "\n".length();
		}
		var r = new Bitfield2D(w, h);

		for (int y = 0, x = 0, ofs = 0, pos = 0; pos < src.length(); )
			if (src.charAt(pos) == '\n') {
				ofs += r.w - x;
				x = 0; y++;
				pos += "\n".length();
			} else {
				if (src.startsWith(one, pos)) r.rawset(ofs);
				pos += one.length();
				x++; ofs++;
			}
		return r;
	}

	public boolean[][] toBool2D() { return toBool2D(0, 0, w, h); }
	public boolean[][] toBool2D(int atx, int aty, int w, int h) {
		validateRect(this.w, this.h, atx, aty, w, h);
		boolean[][] r = Bool2D.create(w, h);
		for (int y = 0, ofs = aty * this.w + atx; y < h; y++, ofs += this.w - w)
			for (int x = 0; x < w; x++, ofs++)
				r[y][x] = rawget(ofs);
		return r;
	}
}

class Bool2D {
	public static boolean[][] create(int w, int h) {
		Bitfield2D.validateSize(w, h);
		if (h == 0) throw Util.BadArgf("boolean[][] can't have zero height.");
		return new boolean[h][w];
	}

	public static void or(boolean[][] it, boolean[][] b, int itX, int itY) {
		or(it, b, 0, 0, b[0].length, b.length, itX, itY);
	}

	public static void or(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
			for (int dx = 0, iItX = ward.destX, iBx = ward.srcX; dx < ward.w; dx++, iItX++, iBx++)
				it[iItY][iItX] |= b[iBy][iBx];
	}

	public static void andNot(boolean[][] it, boolean[][] b, int itX, int itY) {
		andNot(it, b, 0, 0, b[0].length, b.length, itX, itY);
	}

	public static void andNot(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
			for (int dx = 0, iItX = ward.destX, iBx = ward.srcX; dx < ward.w; dx++, iItX++, iBx++)
				it[iItY][iItX] &= !b[iBy][iBx];
	}

	public static void copyFrom(boolean[][] it, boolean[][] b, int itX, int itY) {
		copyFrom(it, b, 0, 0, b[0].length, b.length, itX, itY);
	}

	public static void copyFrom(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
		if (ward.w <= 0) return;
		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
			System.arraycopy(b[iBy], ward.srcX, it[iItY], ward.destX, ward.w);
	}

	public static String toString(boolean[][] it) {
		return toString(it, "##", "..");
	}

	public static String toString(boolean[][] it, String one, String zero) {
		return toBitfield2D(it).toString(one, zero);
	}

	public static boolean[][] parse(String src) { return parse(src, "##"); }
	public static boolean[][] parse(String src, String one) {
		return Bitfield2D.parse(src, one).toBool2D();
	}

	public static Bitfield2D toBitfield2D(boolean[][] it) { return toBitfield2D(it, 0, 0, it[0].length, it.length); }
	public static Bitfield2D toBitfield2D(boolean[][] it, int atx, int aty, int w, int h) {
		Bitfield2D.validateRect(it[0].length, it.length, atx, aty, w, h);
		var r = new Bitfield2D(w, h);
		for (int y = 0, rOfs = 0; y < h; y++)
			for (int x = 0; x < w; x++, rOfs++)
				if (it[y][x]) r.rawset(rOfs);
		return r;
	}
}

class Ideone
{
	// Auto-growing bitfield for procedural generation when resulting size is impractical to predict.
	static class ProcBitfield2D {
		Bitfield2D b = new Bitfield2D(0, 0);
		int ax, ay, bx, by, boundAx, boundAy, boundBx, boundBy;

		void set(int x, int y) {
			if (boundAx == boundBx) {
				ax = x; ay = y; bx = x; by = y;
				boundAx = x; boundAy = y; boundBx = x; boundBy = y;
			}
			if (x < ax || y < ay || x >= bx || y >= by)
				grow(
					x < ax ? growStgy(ax - x, bx - ax) : 0,
					y < ay ? growStgy(ay - y, by - ay) : 0,
					x >= bx ? growStgy(x - bx + 1, bx - ax) : 0,
					y >= by ? growStgy(y - by + 1, by - ay) : 0);
			if (x < boundAx) boundAx = x;
			if (x >= boundBx) boundBx = x + 1;
			if (y < boundAy) boundAy = y;
			if (y >= boundBy) boundBy = y + 1;
			b.set(x-ax, y-ay);
		}

		void unset(int x, int y) {
			if (x >= boundAx && x < boundBx && x >= boundAy && x < boundBy)
				b.unset(x-ax, y-ay);
		}

		void set(int x, int y, boolean value) { if (value) set(x, y); else unset(x, y); }

		static int growStgy(int atLeast, int present) {
			return max(max(8, present / 2), atLeast);
		}

		void grow(int Lx, int Ly, int Rx, int Ry) {
			this.b = new Bitfield2D((bx - ax) + Lx + Rx, (by - ay) + Ly + Ry).copyFrom(
				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, (boundAx - ax) + Lx, (boundAy - ay) + Ly);
			ax -= Lx; ay -= Ly; bx += Rx; by += Ry;
		}

		Bitfield2D bake() {
			return new Bitfield2D(boundBx - boundAx, boundBy - boundAy).copyFrom(
				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, 0, 0);
		}
	}

	static Bitfield2D makeSpruce(int size) {
		Util.rangecheck(size, 1, 20, "size");
		var r = new ProcBitfield2D();
		int nSegs = 3+size/4, trunkWidth = 1+size/3*2;
		int y = 0;
		for (int iSeg = 0; iSeg < nSegs; iSeg++) {
			int maxSegWidth = trunkWidth + 2 * (size + iSeg * size / 2);
			int segWidth = iSeg == 0 ? 1 : trunkWidth + (size + iSeg)/3*2;
			for (; segWidth < maxSegWidth; segWidth += 2) {
				for (int x = -segWidth/2; x < (segWidth+1)/2; x++)
					r.set(x, y);
				y += 1;
			}
		}
		for (int yTrunk = 0; yTrunk < size; yTrunk++) {
			for (int x = -trunkWidth/2; x < (trunkWidth + 1)/2; x++)
				r.set(x, y);
			y++;
		}
		return r.bake();
	}

	static Bitfield2D moon = Bitfield2D.parse(
		"....######..........\n" +
		"..####..............\n" +
		"####................\n" +
		"####................\n" +
		"####................\n" +
		"####..............##\n" +
		"######..........####\n" +
		"..################..\n" +
		"....############", "##");

	static Bitfield2D paintBitfield2D() {
		var r = new Bitfield2D(50, 40);
		r.or(moon, 11, 4);
		r.or(makeSpruce(4), -1, 15);
		r.or(makeSpruce(3), 29, 17);
		r.or(makeSpruce(2), 18, 18);
		r.or(makeSpruce(5), 32, 16);
		var rand = new Random(7);
		for (int iSnowflake = 0; iSnowflake < 25; iSnowflake++) {
			int x = rand.nextInt(r.width()),
				y = min(r.height() - 1, (int) (r.height() * pow(rand.nextFloat(), 2.0)));
			r.set(x, y, !r.get(x, y));
		}
		return r;
	}

	static boolean[][] paintBool2D() {
		var r = Bool2D.create(50, 40);
		Bool2D.or(r, moon.toBool2D(), 11, 4);
		Bool2D.or(r, makeSpruce(4).toBool2D(), -1, 15);
		Bool2D.or(r, makeSpruce(3).toBool2D(), 29, 17);
		Bool2D.or(r, makeSpruce(2).toBool2D(), 18, 18);
		Bool2D.or(r, makeSpruce(5).toBool2D(), 32, 16);
		var rand = new Random(7);
		for (int iSnowflake = 0; iSnowflake < 25; iSnowflake++) {
			int x = rand.nextInt(r[0].length),
				y = min(r.length - 1, (int) (r.length * pow(rand.nextFloat(), 2.0)));
			r[y][x] = !r[y][x];
		}
		return r;
	}

	static Bitfield2D makeRandomBitfield(int w, int h, Random rand) {
		var r = new Bitfield2D(w, h);
		for (int i = 0; i < w*h/5; i++) {
			r.set(rand.nextInt(w), rand.nextInt(h));
		}
		return r;
	}

	static enum Op { OR, AND_NOT, COPY }

	static class PlanItem {
		Op op;
		int rectIndex;
		int rectX, rectY, w, h, destX, destY;

		static PlanItem random(Random rand, Bitfield2D canvas, Bitfield2D[] rects) {
			var r = new PlanItem();
			r.op = Op.values()[rand.nextInt(Op.values().length)];

			r.rectIndex = rand.nextInt(rects.length);
			var rect = rects[r.rectIndex];
			if (rand.nextInt(2) == 0) {
				r.rectX = rand.nextInt(rect.width());
				r.rectY = rand.nextInt(rect.height());
				r.w = 1 + rand.nextInt(rect.width() - r.rectX);
				r.h = 1 + rand.nextInt(rect.height() - r.rectY);
				r.destX = -rect.width() + rand.nextInt(canvas.width() + rect.width() + 1);
				r.destY = -rect.height() + rand.nextInt(canvas.height() + rect.height() + 1);
			} else {
				r.rectX = 0;
				r.rectY = 0;
				r.w = rect.width();
				r.h = rect.height();
				r.destX = rand.nextInt(canvas.width() - rect.width());
				r.destY = rand.nextInt(canvas.height() - rect.height());
			}
			return r;
		}
	}

	static void fusedBenchmarkTest() {
		Random rand = new Random(0);
		Bitfield2D bitCanvas = new Bitfield2D(1000, 1000);
		boolean[][] boolCanvas = Bool2D.create(bitCanvas.width(), bitCanvas.height());
		Bitfield2D bitCanvasBATCH = new Bitfield2D(bitCanvas.width(), bitCanvas.height());

		Bitfield2D[] bitRects = new Bitfield2D[1000];
		boolean[] [][] boolRects = new boolean[bitRects.length][][];
		for (int i = 0; i < bitRects.length; i++) {
			bitRects[i] = makeRandomBitfield(1 + rand.nextInt(bitCanvas.width()/10), 1 + rand.nextInt(bitCanvas.height()/10), rand);
			boolRects[i] = bitRects[i].toBool2D();
		}

		PlanItem[] plan = new PlanItem[600000];
		for (int i = 0; i < plan.length; i++)
			plan[i] = PlanItem.random(rand, bitCanvas, bitRects);

		final int TRIALS = 3;
		for (int iTrial = 0; iTrial < TRIALS; iTrial++) {
			System.out.printf("%s--- TRIAL %d/%d ---\n", iTrial > 0 ? "\n" : "", 1 + iTrial, TRIALS);
			double refTime = benchmark("boolean[][]", () -> {
					for (int i = 0; i < plan.length; i++) {
						switch (plan[i].op) {
							case OR: Bool2D.or(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
							case AND_NOT: Bool2D.andNot(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
							case COPY: default: Bool2D.copyFrom(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
						}
					}
					return boolCanvas;
				});

			benchmark("Bitfield2D (per-bit)", () -> {
				for (int i = 0; i < plan.length; i++) {
					switch (plan[i].op) {
						case OR: bitCanvas.or(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
						case AND_NOT: bitCanvas.andNot(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
						case COPY: default: bitCanvas.copyFrom(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
					}
				}
				return bitCanvas;
			}, refTime);

			benchmark("Bitfield2D (bitsizeof(int) batches)", () -> {
				for (int i = 0; i < plan.length; i++) {
					switch (plan[i].op) {
						case OR: bitCanvasBATCH.orBATCH(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
						case AND_NOT: bitCanvasBATCH.andNotBATCH(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
						case COPY: default: bitCanvasBATCH.copyFrom(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
					}
				}
				return bitCanvasBATCH;
			}, refTime);

			if (iTrial == 0) {
				String ref = Bool2D.toString(boolCanvas);
				if (!bitCanvas.toString().equals(ref))
					throw new RuntimeException("Bitfield2D(per-bit) and boolean[][] do differ.");
				if (!bitCanvasBATCH.toString().equals(ref))
					throw new RuntimeException("Bitfield2D(bitsizeof(int) batches) and boolean[][] do differ.");
			}
		}
	}

	@FunctionalInterface
	interface BenchmarkPayload {
		abstract Object run();
	}

	static double benchmark(String title, BenchmarkPayload payload) {
		return benchmark(title, payload, -1);
	}

	static double benchmark(String title, BenchmarkPayload payload, double refTime) {
		long start = System.nanoTime();
		Object keepAlive = payload.run();
		double time = (System.nanoTime() - start) * 1e-9;
		System.out.println(String.format(
			"%s: %.2f s%s",
			title, time, refTime >= 0 ? String.format(" (%s)", judgement(time, refTime)) : "", keepAlive));
		return time;
	}

	static String judgement(double time, double refTime) {
		final double absThreshold = 0.3, relThreshold = .1;

		return time <= absThreshold || refTime <= absThreshold ?
			String.format("can't judge, min. required time is %.1f s", absThreshold) :
			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
			String.format("%.0f%% %s",
				Math.abs((time < refTime ? refTime / time : time / refTime) - 1) * 100,
				time < refTime ? "faster" : "slower") :
			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		try {
			var image = paintBitfield2D();
			var im2 = paintBool2D();
			if (!image.toString().equals(Bool2D.toString(im2))) {
				throw new RuntimeException(String.format("paintBool2D =\n%s\n\nyet paintBitfield2D =\n%s", im2, image));
			}
			fusedBenchmarkTest();
			System.out.printf("\n%s\n\n", image);
		} catch (Exception e) {
			System.out.println(Util.trace(e));
		}
	}
}