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 Pair floorPair(NavigableMap map, A key) { if (map == null) return null; var e = map.floorEntry(key); return mapEntryToPair(e); } static Pair mapEntryToPair(Map.Entry e) { return e == null ? null : pair(e.getKey(), e.getValue()); } static Pair pair(A a, B b) { return new Pair(a, b); } static Pair pair(A a) { return new Pair(a, a); } static class Pair implements Comparable> { A a; B b; Pair() {} Pair(A a, B b) { this.b = b; this.a = a;} public int hashCode() { return hashCodeFor(a) + 2*hashCodeFor(b); } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Pair)) return false; Pair t = (Pair) o; return eq(a, t.a) && eq(b, t.b); } public String toString() { return "<" + a + ", " + b + ">"; } public int compareTo(Pair p) { if (p == null) return 1; int i = ((Comparable) a).compareTo(p.a); if (i != 0) return i; return ((Comparable) b).compareTo(p.b); } } static int hashCodeFor(Object a) { return a == null ? 0 : a.hashCode(); } static boolean eq(Object a, Object b) { return a == b || a != null && b != null && a.equals(b); } static String str(Object o) { return o == null ? "null" : o.toString(); } static String str(char[] c) { return new String(c); } }