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.*;
class main {


  static DoublePt addDoublePts(DoublePt a, DoublePt b) {
    return a == null ? b : b == null ? a : doublePt(a.x_double()+b.x_double(), a.y_double()+b.y_double());
  }


  static IDoublePt addDoublePts(IDoublePt a, IDoublePt b) {
    return a == null ? b : b == null ? a : doublePt(a.x_double()+b.x_double(), a.y_double()+b.y_double());
  }


static DoublePt doublePt(double x) { return doublePt(x, x); }
static DoublePt doublePt(double x, double y) {
  return new DoublePt(x, y);
}




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 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(long l) {
  return Long.hashCode(l);
}

static int hashCode(double d) {
  return Double.hashCode(d);
}


static double sqrt(double x) {
  return Math.sqrt(x);
}



}