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 javax.imageio.*; import java.math.*; // out of full long range (including negative values) class main { static long randomLong() { return defaultRandomGenerator().nextLong(); } static long randomLong(Random random) { return random.nextLong(); } // returns number between 0 and max-1 static long randomLong(long max) { return randomLong(defaultRandomGenerator(), max); } static long randomLong(Random random, long max) { return mod(randomLong(random), max); } // min <= value < max static long random(long min, long max) { return min+randomLong(max-min); } static Random defaultRandomGenerator() { return ThreadLocalRandom.current(); } // better modulo that gives positive numbers always static int mod(int n, int m) { return (n % m + m) % m; } static long mod(long n, long m) { return (n % m + m) % m; } static BigInteger mod(BigInteger n, int m) { return n.mod(bigint(m)); } static double mod(double n, double m) { return (n % m + m) % m; } static BigInteger bigint(String s) { return new BigInteger(s); } static BigInteger bigint(long l) { return BigInteger.valueOf(l); } }