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 java.util.function.*;
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 java.awt.geom.*;
import javax.imageio.*;
import java.math.*;
import java.time.Duration;
class main {
static LineThroughPoint perpendicularBisector(IDoublePt a, IDoublePt b) {
DoublePt midpoint = doublePt((a.x_double()+b.x_double())/2, (a.y_double()+b.y_double())/2);
double angle = atan2(b.y_double()-a.y_double(), a.x_double()-b.x_double());
return new LineThroughPoint(midpoint, angle);
}
static DoublePt doublePt(double x) { return doublePt(x, x); }
static DoublePt doublePt(double x, double y) {
return new DoublePt(x, y);
}
static double atan2(double x, double y) {
return Math.atan2(x, y);
}
// line that goes through x, y at specified angle
// angle is in radians
static class LineThroughPoint implements IFieldsToList{
static final String _fieldOrder = "x y angle";
double x;
double y;
double angle;
LineThroughPoint() {}
LineThroughPoint(double x, double y, double angle) {
this.angle = angle;
this.y = y;
this.x = x;}
public String toString() { return shortClassName_dropNumberPrefix(this) + "(" + x + ", " + y + ", " + angle + ")"; }
public boolean equals(Object o) {
if (!(o instanceof LineThroughPoint)) return false;
LineThroughPoint __1 = (LineThroughPoint) o;
return x == __1.x && y == __1.y && angle == __1.angle;
}
public int hashCode() {
int h = -2021865473;
h = boostHashCombine(h, _hashCode(x));
h = boostHashCombine(h, _hashCode(y));
h = boostHashCombine(h, _hashCode(angle));
return h;
}
public Object[] _fieldsToList() { return new Object[] {x, y, angle}; }
LineThroughPoint(IDoublePt p, double angle) {
this.angle = angle;
x = p.x_double();
y = p.y_double();
}
}
static class DoublePt implements IDoublePt {
double x, y;
DoublePt() {}
DoublePt(Point p) {
x = p.x;
y = p.y;
}
DoublePt(double x, double y) {
this.y = y;
this.x = x;}
public boolean equals(Object p) { if (p instanceof DoublePt) { return x == ((DoublePt) p).x && y == ((DoublePt) p).y; } return false; }
public int hashCode() {
return boostHashCombine(main.hashCode(x), main.hashCode(y));
}
public String toString() {
return x + ", " + y;
}
double length() { return sqrt(x*x+y*y); }
public double x_double() { return x; }
public double y_double() { return y; }
}
interface IDoublePt {
public double x_double();
public double y_double();
}
static interface IFieldsToList {
Object[] _fieldsToList();
}
static String shortClassName_dropNumberPrefix(Object o) {
return dropNumberPrefix(shortClassName(o));
}
static int boostHashCombine(int a, int b) {
return a ^ (b + 0x9e3779b9 + (a << 6) + (a >>> 2));
// OLD (changed) 2022/3/10: ret a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2));
}
static int _hashCode(Object a) {
return a == null ? 0 : a.hashCode();
}
static int hashCode(Object a) {
return a == null ? 0 : a.hashCode();
}
static int hashCode(long l) {
return Long.hashCode(l);
}
static int hashCode(double d) {
return Double.hashCode(d);
}
static double sqrt(double x) {
return Math.sqrt(x);
}
static String dropNumberPrefix(String s) {
return dropFirst(s, indexOfNonDigit(s));
}
static String shortClassName(Object o) {
if (o == null) return null;
Class c = o instanceof Class ? (Class) o : o.getClass();
String name = c.getName();
return shortenClassName(name);
}
static String[] dropFirst(int n, String[] a) {
return drop(n, a);
}
static String[] dropFirst(String[] a) {
return drop(1, a);
}
static Object[] dropFirst(Object[] a) {
return drop(1, a);
}
static List dropFirst(List l) {
return dropFirst(1, l);
}
static List dropFirst(int n, Iterable i) { return dropFirst(n, toList(i)); }
static List dropFirst(Iterable i) { return dropFirst(toList(i)); }
static List dropFirst(int n, List l) {
return n <= 0 ? l : new ArrayList(l.subList(Math.min(n, l.size()), l.size()));
}
static List dropFirst(List l, int n) {
return dropFirst(n, l);
}
static String dropFirst(int n, String s) { return substring(s, n); }
static String dropFirst(String s, int n) { return substring(s, n); }
static String dropFirst(String s) { return substring(s, 1); }
static int indexOfNonDigit(String s) {
int n = l(s);
for (int i = 0; i < n; i++)
if (!isDigit(s.charAt(i)))
return i;
return -1;
}
static String shortenClassName(String name) {
if (name == null) return null;
int i = lastIndexOf(name, "$");
if (i < 0) i = lastIndexOf(name, ".");
return i < 0 ? name : substring(name, i+1);
}
static String[] drop(int n, String[] a) {
n = Math.min(n, a.length);
String[] b = new String[a.length-n];
System.arraycopy(a, n, b, 0, b.length);
return b;
}
static Object[] drop(int n, Object[] a) {
n = Math.min(n, a.length);
Object[] b = new Object[a.length-n];
System.arraycopy(a, n, b, 0, b.length);
return b;
}
static ArrayList toList(A[] a) { return asList(a); }
static ArrayList toList(int[] a) { return asList(a); }
static ArrayList toList(Set s) { return asList(s); }
static ArrayList toList(Iterable s) { return asList(s); }
static String substring(String s, int x) {
return substring(s, x, strL(s));
}
static String substring(String s, int x, int y) {
if (s == null) return null;
if (x < 0) x = 0;
int n = s.length();
if (y < x) y = x;
if (y > n) y = n;
if (x >= y) return "";
return s.substring(x, y);
}
// convenience method for quickly dropping a prefix
static String substring(String s, CharSequence l) {
return substring(s, lCharSequence(l));
}
static int l(Object[] a) { return a == null ? 0 : a.length; }
static int l(boolean[] a) { return a == null ? 0 : a.length; }
static int l(byte[] a) { return a == null ? 0 : a.length; }
static int l(short[] a) { return a == null ? 0 : a.length; }
static int l(long[] a) { return a == null ? 0 : a.length; }
static int l(int[] a) { return a == null ? 0 : a.length; }
static int l(float[] a) { return a == null ? 0 : a.length; }
static int l(double[] a) { return a == null ? 0 : a.length; }
static int l(char[] a) { return a == null ? 0 : a.length; }
static int l(Collection c) { return c == null ? 0 : c.size(); }
static int l(Iterator i) { return iteratorCount_int_close(i); } // consumes the iterator && closes it if possible
static int l(Map m) { return m == null ? 0 : m.size(); }
static int l(CharSequence s) { return s == null ? 0 : s.length(); }
static long l(File f) { return f == null ? 0 : f.length(); }
static boolean isDigit(char c) {
return Character.isDigit(c);
}
static int lastIndexOf(String a, String b) {
return a == null || b == null ? -1 : a.lastIndexOf(b);
}
static int lastIndexOf(String a, char b) {
return a == null ? -1 : a.lastIndexOf(b);
}
// starts searching from i-1
static int lastIndexOf(List l, int i, A a) {
if (l == null) return -1;
for (i = min(l(l), i)-1; i >= 0; i--)
if (eq(l.get(i), a))
return i;
return -1;
}
static int lastIndexOf(List l, A a) {
if (l == null) return -1;
for (int i = l(l)-1; i >= 0; i--)
if (eq(l.get(i), a))
return i;
return -1;
}
// unclear semantics as to whether return null on null
static ArrayList asList(A[] a) {
return a == null ? new ArrayList() : new ArrayList(Arrays.asList(a));
}
static ArrayList asList(int[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (int i : a) l.add(i);
return l;
}
static ArrayList asList(long[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (long i : a) l.add(i);
return l;
}
static ArrayList asList(float[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (float i : a) l.add(i);
return l;
}
static ArrayList asList(double[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (double i : a) l.add(i);
return l;
}
static ArrayList asList(short[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (short i : a) l.add(i);
return l;
}
static ArrayList asList(Iterator it) {
ArrayList l = new ArrayList();
if (it != null)
while (it.hasNext())
l.add(it.next());
return l;
}
// disambiguation
static ArrayList asList(IterableIterator s) {
return asList((Iterator) s);
}
static ArrayList asList(Iterable s) {
if (s instanceof ArrayList) return (ArrayList) s;
ArrayList l = new ArrayList();
if (s != null)
for (A a : s)
l.add(a);
return l;
}
static ArrayList asList(Enumeration e) {
ArrayList l = new ArrayList();
if (e != null)
while (e.hasMoreElements())
l.add(e.nextElement());
return l;
}
static int strL(String s) {
return s == null ? 0 : s.length();
}
static int lCharSequence(CharSequence s) {
return s == null ? 0 : s.length();
}
static int iteratorCount_int_close(Iterator i) { try {
int n = 0;
if (i != null) while (i.hasNext()) { i.next(); ++n; }
if (i instanceof AutoCloseable) ((AutoCloseable) i).close();
return n;
} catch (Exception __e) { throw rethrow(__e); } }
static int min(int a, int b) {
return Math.min(a, b);
}
static long min(long a, long b) {
return Math.min(a, b);
}
static float min(float a, float b) { return Math.min(a, b); }
static float min(float a, float b, float c) { return min(min(a, b), c); }
static double min(double a, double b) {
return Math.min(a, b);
}
static double min(double[] c) {
double x = Double.MAX_VALUE;
for (double d : c) x = Math.min(x, d);
return x;
}
static float min(float[] c) {
float x = Float.MAX_VALUE;
for (float d : c) x = Math.min(x, d);
return x;
}
static byte min(byte[] c) {
byte x = 127;
for (byte d : c) if (d < x) x = d;
return x;
}
static short min(short[] c) {
short x = 0x7FFF;
for (short d : c) if (d < x) x = d;
return x;
}
static int min(int[] c) {
int x = Integer.MAX_VALUE;
for (int d : c) if (d < x) x = d;
return x;
}
static boolean eq(Object a, Object b) {
return a == b || a != null && b != null && a.equals(b);
}
static ArrayList emptyList() {
return new ArrayList();
//ret Collections.emptyList();
}
static ArrayList emptyList(int capacity) {
return new ArrayList(max(0, capacity));
}
// Try to match capacity
static ArrayList emptyList(Iterable l) {
return l instanceof Collection ? emptyList(((Collection) l).size()) : emptyList();
}
static ArrayList emptyList(Object[] l) {
return emptyList(l(l));
}
// get correct type at once
static ArrayList emptyList(Class c) {
return new ArrayList();
}
static List ll(A... a) {
ArrayList l = new ArrayList(a.length);
if (a != null) for (A x : a) l.add(x);
return l;
}
static RuntimeException rethrow(Throwable t) {
if (t instanceof Error)
_handleError((Error) t);
throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}
static RuntimeException rethrow(String msg, Throwable t) {
throw new RuntimeException(msg, t);
}
static String str(Object o) {
return o == null ? "null" : o.toString();
}
static String str(char[] c) {
return new String(c);
}
static String str(char[] c, int offset, int count) {
return new String(c, offset, count);
}
static int max(int a, int b) { return Math.max(a, b); }
static int max(int a, int b, int c) { return max(max(a, b), c); }
static long max(int a, long b) { return Math.max((long) a, b); }
static long max(long a, long b) { return Math.max(a, b); }
static double max(int a, double b) { return Math.max((double) a, b); }
static float max(float a, float b) { return Math.max(a, b); }
static double max(double a, double b) { return Math.max(a, b); }
static > A max (Iterable l) {
A max = null;
var it = iterator(l);
if (it.hasNext()) {
max = it.next();
while (it.hasNext()) {
A a = it.next();
if (cmp(a, max) > 0)
max = a;
}
}
return max;
}
/*Nah.
static int max(Collection c) {
int x = Integer.MIN_VALUE;
for (int i : c) x = max(x, i);
ret x;
}*/
static double max(double[] c) {
if (c.length == 0) return Double.MIN_VALUE;
double x = c[0];
for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
return x;
}
static float max(float[] c) {
if (c.length == 0) return Float.MAX_VALUE;
float x = c[0];
for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
return x;
}
static byte max(byte[] c) {
byte x = -128;
for (byte d : c) if (d > x) x = d;
return x;
}
static short max(short[] c) {
short x = -0x8000;
for (short d : c) if (d > x) x = d;
return x;
}
static int max(int[] c) {
int x = Integer.MIN_VALUE;
for (int d : c) if (d > x) x = d;
return x;
}
static > A max(A a, A b) {
return cmp(a, b) >= 0 ? a : b;
}
static void _handleError(Error e) {
//call(javax(), '_handleError, e);
}
static Iterator iterator(Iterable c) {
return c == null ? emptyIterator() : c.iterator();
}
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 Iterator emptyIterator() {
return Collections.emptyIterator();
}
// you still need to implement hasNext() and next()
static abstract class IterableIterator implements Iterator, Iterable {
public Iterator iterator() {
return this;
}
public void remove() {
unsupportedOperation();
}
}
static UnsupportedOperationException unsupportedOperation() {
throw new UnsupportedOperationException();
}
}