import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
class main {
static String formatDoubleRect(int digits, DoubleRect r) {
return r == null ? str(r) : formatDouble(r.x, digits) + "/" + formatDouble(r.y, digits) + ", size: " + formatDouble(r.w, digits) + "/" + formatDouble(r.h, digits);
}
static String str(Object o) {
return o == null ? "null" : o.toString();
}
static String str(char[] c) {
return new String(c);
}
static String formatDouble(double d, int digits) {
String format = digits <= 0 ? "0" : "0." + rep(digits, '#');
return decimalFormatEnglish(format, d);
}
static String formatDouble(double d) {
return str(d);
}
static String rep(int n, char c) {
return repeat(c, n);
}
static String rep(char c, int n) {
return repeat(c, n);
}
static List rep(A a, int n) {
return repeat(a, n);
}
static List rep(int n, A a) {
return repeat(n, a);
}
static String decimalFormatEnglish(String format, double d) {
return decimalFormatEnglish(format).format(d);
}
static java.text.DecimalFormat decimalFormatEnglish(String format) {
return new java.text.DecimalFormat(format, new java.text.DecimalFormatSymbols(Locale.ENGLISH));
}
static String repeat(char c, int n) {
n = Math.max(n, 0);
char[] chars = new char[n];
for (int i = 0; i < n; i++)
chars[i] = c;
return new String(chars);
}
static List repeat(A a, int n) {
n = Math.max(n, 0);
List l = new ArrayList(n);
for (int i = 0; i < n; i++)
l.add(a);
return l;
}
static List repeat(int n, A a) {
return repeat(a, n);
}
static class DoubleRect {
double x, y, w, h;
DoubleRect() {}
DoubleRect(Rectangle r) {
x = r.x;
y = r.y;
w = r.width;
h = r.height;
}
DoubleRect(double x, double y, double w, double h) {
this.h = h;
this.w = w;
this.y = y;
this.x = x;}
// Huh. not implementing equals()/hashCode? Stefan is mysterious
boolean eq(Object o) {
if (!(o instanceof DoubleRect)) return false;
if (o == this) return true;
DoubleRect r = (DoubleRect) o;
return x == r.x && y == r.y && w == r.w && h == r.h;
}
public String toString() {
return x + "," + y + " / " + w + "," + h;
}
double x1() { return x; }
double y1() { return y; }
double x2() { return x + w; }
double y2() { return y + h; }
boolean contains(Pt p) {
return contains(p.x, p.y);
}
boolean contains(double _x, double _y) {
return _x >= x && _y >= y && _x < x+w && _y < y+h;
}
boolean empty() { return w <= 0 || h <= 0; }
}
static class Pt implements Comparable {
int x, y;
Pt() {}
Pt(Point p) {
x = p.x;
y = p.y;
}
Pt(int x, int y) {
this.y = y;
this.x = x;}
Point getPoint() {
return new Point(x, y);
}
public boolean equals(Object o) {
return o instanceof Pt && x == ((Pt) o).x && y == ((Pt) o).y;
}
public int hashCode() {
return boostHashCombine(x, y);
}
// compare in scan order
public int compareTo(Pt p) {
if (y != p.y) return cmp(y, p.y);
return cmp(x, p.x);
}
public String toString() {
return x + ", " + y;
}
}
static boolean contains(Collection c, Object o) {
return c != null && c.contains(o);
}
static boolean contains(Object[] x, Object o) {
if (x != null)
for (Object a : x)
if (eq(a, o))
return true;
return false;
}
static boolean contains(String s, char c) {
return s != null && s.indexOf(c) >= 0;
}
static boolean contains(String s, String b) {
return s != null && s.indexOf(b) >= 0;
}
static boolean contains(BitSet bs, int i) {
return bs != null && bs.get(i);
}
static int boostHashCombine(int a, int b) {
return a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2));
}
static int cmp(Number a, Number b) {
return a == null ? b == null ? 0 : -1 : cmp(a.doubleValue(), b.doubleValue());
}
static int cmp(double a, double b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(int a, int b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(long a, long b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(Object a, Object b) {
if (a == null) return b == null ? 0 : -1;
if (b == null) return 1;
return ((Comparable) a).compareTo(b);
}
static boolean eq(Object a, Object b) {
return a == b || a != null && b != null && a.equals(b);
}
}