結果
| 問題 | No.1611 Minimum Multiple with Double Divisors |
| ユーザー |
 CaliPota
|
| 提出日時 | 2021-07-21 21:41:32 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 26,579 bytes |
| コンパイル時間 | 4,934 ms |
| コンパイル使用メモリ | 92,680 KB |
| 実行使用メモリ | 51,944 KB |
| 最終ジャッジ日時 | 2024-07-17 17:00:36 |
| 合計ジャッジ時間 | 13,707 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 391 ms
51,604 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | AC | 53 ms
37,192 KB |
| testcase_29 | AC | 54 ms
37,244 KB |
| testcase_30 | AC | 53 ms
36,936 KB |
| testcase_31 | AC | 53 ms
37,244 KB |
| testcase_32 | AC | 55 ms
37,096 KB |
| testcase_33 | AC | 54 ms
36,852 KB |
| testcase_34 | AC | 55 ms
36,784 KB |
| testcase_35 | WA | - |
| testcase_36 | AC | 59 ms
37,224 KB |
| testcase_37 | AC | 54 ms
37,180 KB |
| testcase_38 | AC | 54 ms
36,656 KB |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
//@Japanese
/* PriorityQueueは拡張for文で出すとsortされてない順番で出てくる
* longのbit演算は1L<<posに注意
* JOIはMLEが厳しい。最悪shortを使う。
* ArrayListはオートボクシングが遅いから、最悪自作listを使う
*/
/*略語
* 2-to, 4-for, 8-from
* -L -long(型), -P -素数Pを法とした余り
* a,b -任意の引数, n,m -自然数, p -素数
* pos -postition
* abs -絶対値
* min -minimum, max -maximum, ave -average
* div -divide
* pow -power(累乗)
* ceil -ceiling(天井関数)
* dt -data
* ln -length
* sc -scanner
* INF -INFINITY
* e97 -10E9+7=1000000007(prime often used)
*/
// How about n=1, h*w=1*x
// n(E) < 10^6 ? ok : create new Vertex
public class Main {
public static void main(String[] args) throws Exception {
FastScanner sc = new FastScanner();
PrintWriter out = new PrintWriter(System.out);
long[] ps = {2L,3L,5L,7L,11L,13L,17L,19L,23L,29L,31L,37L};//12
int T = sc.nexI();
for(int t=0; t<T; t++) {
long n = sc.nexL();
long[] dt = new long[12];
fill(dt,1L);
for(int i=0; i<12; i++) {
long n2 = n;
while(n2%ps[i] == 0L) {
dt[i] *= ps[i];
n2 /= ps[i];
}
dt[i] *= ps[i];
}
n *= minAll(dt);
out.println(n);
}
out.flush();
return;
}
static class Net { // @Japanese 重みなしグラフ
private ArrayList<Node0n> dt = new ArrayList<>();
Net(int sz) {
for (int i = 0; i < sz; i++) {
Node0n node1 = new Node0n();
dt.add(node1);
}
}
public void add(int v8, int cnct2) {
dt.get(v8).add(cnct2);
}
public void add2(int v1, int v2) {
dt.get(v1).add(v2);
dt.get(v2).add(v1);
}
public HashSet<Integer> get(int v) {
return dt.get(v).getAll();
}
public int size() {
return dt.size();
}
public int sizeOf(int v) {
return dt.get(v).size();
}
public void remove(int v, int e) {
dt.get(v).remove(e);
}
public void clear() {
for (int i = 0; i < dt.size(); i++)
dt.get(i).clear();
}
public void clear(int v) {
dt.get(v).clear();
}
public static Net make_tree(int tree_size, FastScanner sc) {
Net tree = new Net(tree_size);
for (int i = 1; i < tree_size; i++) {
int s1 = sc.nexI() - 1;
int g1 = sc.nexI() - 1;
tree.add2(s1, g1);
}
return tree;
}
public static Net make_net(int vn, int en, FastScanner sc) {
Net g = new Net(vn);
for (int i = 0; i < en; i++) {
int s1 = sc.nexI() - 1;
int g1 = sc.nexI() - 1;
g.add2(s1, g1);
}
return g;
}
private void add_v(Node0n v_new) {
dt.add(v_new);
}
private int[] get_parent_bfs(int root) {
int[] ans = new int[this.dt.size()];
fill(ans, -1);
ans[root] = INF;
ArrayDeque<Integer> todo = new ArrayDeque<>();
todo.add(root);
while (!todo.isEmpty()) {
int dw = todo.poll();
for (int e : this.get(dw)) {
if (ans[e] < 0) {
ans[e] = dw;
todo.add(e);
}
}
}
return ans;
}
private int[] get_dist_bfs(int root) {
int[] ans = new int[this.dt.size()];
fill(ans, -1);
ans[root] = 0;
ArrayDeque<Integer> todo = new ArrayDeque<>();
todo.add(root);
while (!todo.isEmpty()) {
int dw = todo.poll();
for (int e : this.get(dw)) {
if (ans[e] < 0) {
ans[e] = ans[dw]+1;
todo.add(e);
}
}
}
return ans;
}
private ArrayList<Integer> get_leaf_list(int exclude) {
ArrayList<Integer> ans = new ArrayList<>();
for (int i = 0; i < this.dt.size(); i++) {
if (i == exclude)
continue;
if (this.sizeOf(i) == 1)
ans.add(i);
}
return ans;
}
public void show2() {
for (int i = 0; i < dt.size(); i++) {
System.out.print(i + ":");
for (int e : dt.get(i).getAll())
System.out.print(" " + e);
System.out.println();
}
}
}
static class Node0n { // @Japanese 重みなしグラフの頂点
private HashSet<Integer> next_vs = new HashSet<>();
public void add(int cnct2) {
next_vs.add(cnct2);
}
public HashSet<Integer> getAll() {
return next_vs;
}
public int size() {
return next_vs.size();
}
public void remove(int e) {
next_vs.remove(e);
}
public void clear() {
next_vs.clear();
}
public void addAll(Node0n list2add) {
this.next_vs.addAll(list2add.next_vs);
}
}
private static final int INF = (int) 3e8;
private static final long INFL = (long) 1e17;
private static final int INTMAX = Integer.MAX_VALUE;
private static final long LONGMAX = Long.MAX_VALUE;
private static final long e97 = 1000000007L;
private static final long e99 = 998244353L;
private static final double PI = Math.PI;
private static void prYN(boolean ans, PrintWriter out) {
if(ans) out.println("YES");
else out.println("NO");
}
private static void prYn(boolean ans) {
if(ans) System.out.println("Yes");
else System.out.println("No");
}
private static void pryesno(boolean ans) {
if(ans) System.out.println("yes");
else System.out.println("no");
}
private static void assertion(boolean should_true) {
// throw Error if should_true is not true @Japanese「断言」
if (!should_true)
throw new AssertionError();
}
private static int abs(int a) {
return (a >= 0) ? a : -a;
}
private static long abs(long a) {
return (a >= 0L) ? a : -a;
}
private static double abs(double a) {
return (a >= 0.0) ? a : -a;
}
private static int getsign(long a) {
if(a>0) return 1;
else if(a==0) return 0;
else return -1;
}
private static int min(int a, int b) {
return (a < b) ? a : b;
}
private static long min(long a, long b) {
return (a < b) ? a : b;
}
private static double min(double a, double b) {
return (a < b) ? a : b;
}
private static int max(int a, int b) {
return (a > b) ? a : b;
}
private static long max(long a, long b) {
return (a > b) ? a : b;
}
private static double max(double a, double b) {
return (a > b) ? a : b;
}
private static int pow2(int num2pow) {
if (num2pow > 4e4)
throw new IllegalArgumentException("Input is to Large. Use Long.");
return num2pow * num2pow;
}
private static long pow2(long num2pow) {
if (num2pow > 1e8)
throw new IllegalArgumentException("Input is to Large. Use PowP.");
return num2pow * num2pow;
}
private static int pow(int num_powered, int index) {
int ans = 1;
for (int i = 0; i < index; i++) {
if (ans >= (INTMAX / num_powered))
throw new IllegalArgumentException("Input is to Large. Use Long.");
ans *= num_powered;
}
return ans;
}
private static long pow(long num_powered, int index) {
long ans = 1L;
for (int i = 0; i < index; i++) {
if (ans >= (LONGMAX / num_powered))
throw new IllegalArgumentException("Input is to Large. Use PowP.");
ans *= num_powered;
}
return ans;
}
private static long powP(long num_powered, long index, long p) {
// O(log(index))
// @Japanese 繰り返し二乗法
if (index == 0L)
return 1L;
if (index == 2L) {
return (pow2(num_powered) % p);
}
if (num_powered == 0L)
return 0L;
int d = getDigit2(index);
long[] num_done_by2 = new long[d + 1];
num_done_by2[0] = num_powered;
for (int i = 1; i <= d; i++) {
num_done_by2[i] = num_done_by2[i - 1] * num_done_by2[i - 1];
num_done_by2[i] %= p;
}
long ans = 1L;
for (int i = d; i >= 0; i--) {
long cf = (1L << (long) i);
if (index >= cf) {
index -= cf;
ans = ans * num_done_by2[i];
ans %= p;
}
}
return ans;
}
private static double hypod(double a, double b) {
return Math.sqrt(a * a + b * b);
}
private static int getDigit2(long num2know) {
// O(log(n))
long compare4 = 1L;
int digit = 0;
while (num2know >= compare4) {
digit++;
compare4 = (1L << (long) digit);
}
return digit;
// num < 2^digit
}
private static int getDigit10(long num2know) {
// O(log10(n))
if(num2know<0L) throw new IllegalArgumentException("Input is Negative");
if(num2know>=1000000000000000000L) return 19;
long compare4 = 1L;
int digit = 0;
while (num2know >= compare4) {
digit++;
compare4 *= 10L;
}
return digit; // @Japanese num は digit桁の数で、10^digit未満
}
private static int divceil(int numerator, int denominator) {
return (numerator + denominator - 1) / denominator;
}
private static long divceil(long numerator, long denominator) {
return (numerator + denominator - 1L) / denominator;
}
private static long factorial(int n) {
// O(n)
long ans = 1L;
for (long i = 2; i <= n; i++) {
if (ans >= (LONGMAX / i))
throw new IllegalArgumentException("Input is to Large. Use facP.");
ans *= i;
}
return ans;
}
private static long facP(int n, long p) {
// O(n) see also PermulationCombination:O(max_sz)+Q
long ans = 1L;
for (long i = 2; i <= n; i++) {
ans *= i;
ans %= p;
}
return ans;
}
private static long lcm(long m, long n) {
long ans = m / gcd(m, n);
if (ans >= (LONGMAX / n))
throw new IllegalArgumentException("Input is to Large.");
ans *= n;
return ans;
}
private static long gcd(long m, long n) {
// O(log(m+n))
if ((m <= 0L) || (n <= 0L))
throw new IllegalArgumentException("m and n should be natural.");
while ((m > 0L) && (n > 0L)) {
if (m >= n)
m %= n;
else
n %= m;
}
if (m > 0L)
return m;
else
return n;
}
private static boolean is_prime(long n2check) {
// @Japanese O(√n)
if (n2check == 1L)
return false;
for (long i = 2L; i <= Math.sqrt(n2check); i++) {
if (n2check % i == 0L)
return false;
}
return true;
}
private static int isSquare(long n) {
double sq = Math.sqrt(n);
long ans = (long)sq;
if((ans *ans) == n) return (int)ans;
else return -1;
}
private static int safe_mod(int n, int p) {
n %= p;
if (n >= 0)
return n;
return (n + p);
}
private static long safe_mod(long n, long p) {
n %= p;
if (n >= 0L)
return n;
return (n + p);
}
private static long modinv(long n, long p) {
// @Japanese 逆元を求める
// O(10log(n))
// pは素数でなくてもよい
// ネットから拾ってきたのが理解不能だったので、行列計算を用いて非効率的アルゴリズムを書いた
n %= p;
if ((p == 1L) || (gcd(n, p) != 1L))
throw new IllegalArgumentException("n and p should be coprime.");
// @Japanese
// yn≡1(mod p)
// <-> xp+yn=1; (n<p)
// ...(sx+ty)a+(ux+vy)b=1 (|sv-tu|=1)
// ...(sx+ty)a+(ux+vy)=1
// <- sx+ty=0, ux+vy=1
long a = p, b = n, s = 1L, t = 0L, u = 0L, v = 1L;
while (b > 1) {
long quo = a / b, rem = a % b;
a = b;
b = rem;
long s2 = s * quo + u, t2 = t * quo + v;
u = s;
v = t;
s = s2;
t = t2;
}
long det = s * v - t * u;
if (abs(det) != 1L)
throw new ArithmeticException("My algorithm was Wrong!!");
s /= det;
s %= p;
if (s < 0L)
s += p;
return s;
}
private static int minAll(int[] dt4min) {
// O(n)
int min = INF;
for (int element : dt4min) {
if (element < min)
min = element;
}
return min;
}
private static long minAll(long[] dt4min) {
// O(n)
long min = INFL;
for (long element : dt4min) {
if (element < min)
min = element;
}
return min;
}
private static int maxAll(int[] dt4max) {
// O(n)
int max = -INF;
for (int element : dt4max) {
if (element > max)
max = element;
}
return max;
}
private static long maxAll(long[] dt4max) {
// O(n)
long max = -INFL;
for (long element : dt4max) {
if (element > max)
max = element;
}
return max;
}
private static int sumAll(int[] dt4sum) {
// O(n)
int sum_of_dt = 0;
for (int element : dt4sum) {
if (sum_of_dt > (INTMAX - element))
throw new IllegalArgumentException("Input is to Large. Use Long.");
sum_of_dt += element;
}
return sum_of_dt;
}
private static long sumAll(long[] dt4sum) {
// O(n)
long sum_of_dt = 0L;
for (long element : dt4sum) {
if (sum_of_dt > (LONGMAX - element))
throw new IllegalArgumentException("Input is to Large.");
sum_of_dt += element;
}
return sum_of_dt;
}
private static int sumAll(ArrayList<Integer> dt4sum) {
int sum_of_dt = 0;
for (long element : dt4sum) {
if (sum_of_dt > (INTMAX - element))
throw new IllegalArgumentException("Input is to Large. Use Long.");
sum_of_dt += element;
}
return sum_of_dt;
}
private static int[] reverse(int[] as) {
int ln = as.length;
int[] bs = new int[ln];
for (int i = 0; i < ln; i++)
bs[i] = as[ln - i - 1];
return bs;
}
private static long[] reverse(long[] as) {
int ln = as.length;
long[] bs = new long[ln];
for (int i = 0; i < ln; i++)
bs[i] = as[ln - i - 1];
return bs;
}
private static char[] reverse(char[] as) {
int ln = as.length;
char[] bs = new char[ln];
for (int i = 0; i < ln; i++)
bs[i] = as[ln - i - 1];
return bs;
}
private static void reverseSub(int[] as, int S_include, int Gnot_include) {
// O(G-S)
int ln = Gnot_include - S_include;
int[] bs = new int[ln];
for (int i = S_include; i < Gnot_include; i++)
bs[i - S_include] = as[i];
for (int i = 0; i < ln; i++)
as[i + S_include] = bs[ln - i - 1];
}
private static boolean is_in_area(int y, int x, int height, int width) {
if (y < 0)
return false;
if (x < 0)
return false;
if (y >= height)
return false;
if (x >= width)
return false;
return true;
}
private static boolean is_in_area(Vector v, int height, int width) {
if (v.y < 0)
return false;
if (v.x < 0)
return false;
if (v.y >= height)
return false;
if (v.x >= width)
return false;
return true;
}
private static int nC2(int n) {
return ((n * (n - 1)) / 2);
}
private static long nC2(long n) {
return ((n * (n - 1L)) / 2L);
}
private static long nCk_unsafe(int n, int k) {
long ans = factorial(n);
ans /= factorial(k);
ans /= factorial(n-k);
return ans;
}
private static int iflag(int pos) {
if (pos >= 32)
throw new IllegalArgumentException("Input is to Large. Use Long.");
return (1 << pos);
}
private static long flag(int pos) {
if (pos >= 64)
throw new IllegalArgumentException("Input is to Large. Use Long.");
return (1L << (long) pos);
}
private static boolean isFlaged(int bit, int pos) {
if (pos >= 32)
throw new IllegalArgumentException("Input is to Large.");
return ((bit & (1 << pos)) != 0);
}
private static boolean isFlaged(long bit, int pos) {
if (pos >= 64)
throw new IllegalArgumentException("Input is to Large.");
return ((bit & (1L << (long) pos)) != 0L);
}
private static int deflag(int bit, int pos) {
return (bit & (~(1 << pos)));
}
private static int countFlaged(int bit) {
int ans = 0;
for (int i = 0; i < 31; i++) {
if ((bit & (1 << i)) != 0)
ans++;
}
return ans;
}
private static int countFlaged(long bit) {
int ans = 0;
for (long i = 0L; i < 63L; i++) {
if ((bit & (1L << i)) != 0L)
ans++;
}
return ans;
}
private static int[] Xdir4 = { 1, 0, 0, -1 };
private static int[] Ydir4 = { 0, 1, -1, 0 };
private static int[] Xdir8 = { 1, 1, 1, 0, 0, -1, -1, -1 };
private static int[] Ydir8 = { 1, 0, -1, 1, -1, 1, 0, -1 };
public static int biSearch(long[] dt, long target) {
// O(log(dt.length))
// dt should be sorted in 0->INF
// return adress of target
int left = 0, right = dt.length - 1;
int mid = -1;
while (left <= right) {
mid = ((right + left) / 2);
if (dt[mid] == target)
return mid;
if (dt[mid] < target)
left = (mid + 1);
else
right = (mid - 1);
}
return -1;
}
public static int biSearchMax(long[] dt, long target) {
// O(log(dt.length))
// dt should be sorted in 0->INF
int left = -1, right = dt.length, mid = -1;
while ((right - left) > 1) {
mid = ((right + left) / 2);
if (dt[mid] <= target)
left = mid;
else
right = mid;
}
return left;
// @Japanese target以下の最大のaddress
}
public static int biSearchMin(long[] dt, long target) {
// O(log(dt.length))
// dt should be sorted in 0->INF
int left = -1, right = dt.length, mid = -1;
while ((right - left) > 1) {
mid = ((right + left) / 2);
if (dt[mid] <= target)
left = mid;
else
right = mid;
}
return right;
// @Japanese targetより大きい最小のaddress
}
private static void fill(boolean[] target, boolean reset) {
for (int i = 0; i < target.length; i++)
target[i] = reset;
}
private static void fill(int[] target, int reset) {
for (int i = 0; i < target.length; i++)
target[i] = reset;
}
private static void fill(long[] target, long reset) {
for (int i = 0; i < target.length; i++)
target[i] = reset;
}
private static void fill(char[] target, char reset) {
for (int i = 0; i < target.length; i++)
target[i] = reset;
}
private static void fill(double[] target, double reset) {
for (int i = 0; i < target.length; i++)
target[i] = reset;
}
private static void fill(boolean[][] target, boolean reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
target[i][j] = reset;
}
}
}
private static void fill(int[][] target, int reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
target[i][j] = reset;
}
}
}
private static void fill(long[][] target, long reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
target[i][j] = reset;
}
}
}
private static void fill(char[][] target, char reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
target[i][j] = reset;
}
}
}
private static void fill(double[][] target, double reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
target[i][j] = reset;
}
}
}
private static void fill(int[][][] target, int reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
for (int k = 0; k < target[i][j].length; k++) {
target[i][j][k] = reset;
}
}
}
}
private static void fill(long[][][] target, long reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
for (int k = 0; k < target[i][j].length; k++) {
target[i][j][k] = reset;
}
}
}
}
private static void fill(double[][][] target, double reset) {
for (int i = 0; i < target.length; i++) {
for (int j = 0; j < target[i].length; j++) {
for (int k = 0; k < target[i][j].length; k++) {
target[i][j][k] = reset;
}
}
}
}
private static void fill_parent(int[] parent) {
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
private static void showBit(int bit) {
for (int i = 0; i < getDigit2(bit); i++) {
if (isFlaged(bit, i))
System.out.print("O");
else
System.out.print(".");
}
System.out.println();
}
private static void showBit(long bit) {
for (int i = 0; i < getDigit2(bit); i++) {
if (isFlaged(bit, i))
System.out.print("O");
else
System.out.print(".");
}
System.out.println();
}
static void show2(boolean[][] dt, String cmnt) {
for (int i = 0; i < dt.length; i++) {
for (int j = 0; j < dt[i].length; j++) {
if (dt[i][j])
System.out.print("O");
else
System.out.print(".");
}
if (!cmnt.equals(""))
System.out.print("<-" + cmnt);
System.out.println(" :" + i);
}
}
static void show2(int[][] dt, String cmnt) {
for (int i = 0; i < dt.length; i++) {
for (int j = 0; j < dt[i].length; j++)
System.out.print(dt[i][j] + ",");
if (!cmnt.equals(""))
System.out.print("<-" + cmnt);
System.out.println(" :" + i);
}
}
static void show2(long[][] dt, String cmnt) {
for (int i = 0; i < dt.length; i++) {
for (int j = 0; j < dt[i].length; j++)
System.out.print(dt[i][j] + ",");
if (!cmnt.equals(""))
System.out.print("<-" + cmnt);
System.out.println(" :" + i);
}
}
static void show2(ArrayDeque<Long> dt) {
long element = 0;
while (dt.size() > 0) {
element = dt.removeFirst();
System.out.print(element);
}
System.out.println("\n");
}
static void show2(List<Object> dt) {
for (int i = 0; i < dt.size(); i++)
System.out.print(dt.get(i) + ",");
System.out.println("\n");
}
private static void prtlnas(int[] array, PrintWriter out) {
for (int e: array)
out.println(e);
out.flush();
}
private static void prtlnas(long[] array, PrintWriter out) {
for (long e: array)
out.println(e);
out.flush();
}
private static void prtlnas(ArrayList<Object> array, PrintWriter out) {
for (Object e: array)
out.println(e);
out.flush();
}
private static void prtspas(int[] array, PrintWriter out) {
out.print(array[0]);
for (int i = 1; i < array.length; i++)
out.print(" " + array[i]);
out.println();
//out.flush();
}
private static void prtspas(long[] array, PrintWriter out) {
out.print(array[0]);
for (int i = 1; i < array.length; i++)
out.print(" " + array[i]);
out.println();
out.flush();
}
private static void prtspas(double[] array, PrintWriter out) {
out.print(array[0]);
for (int i = 1; i < array.length; i++)
out.print(" " + array[i]);
out.println();
out.flush();
}
private static void prtspas(List<Integer> array, PrintWriter out) {
if (array.isEmpty())
return;
out.print(array.get(0));
for (int i = 1; i < array.size(); i++)
out.print(" " + array.get(i));
out.println();
out.flush();
}
static class Vector {
int x, y;
public Vector(int sx, int sy) {
this.x = sx;
this.y = sy;
}
public boolean equals(Vector v) {
return (this.x == v.x && this.y == v.y);
}
public void show2() {
System.out.println(this.x + ", " + this.y);
}
public static int dist2(Vector a, Vector b) {
int dx = abs(a.x - b.x);
int dy = abs(a.y - b.y);
if (dx > 3e4)
throw new IllegalArgumentException("Input is to Large. Use Long.");
if (dy > 3e4)
throw new IllegalArgumentException("Input is to Large. Use Long.");
return (dx * dx + dy * dy);
}
}
static class LVector {
long x, y;
public LVector(long sx, long sy) {
this.x = sx;
this.y = sy;
}
public boolean equals(LVector v) {
return (this.x == v.x && this.y == v.y);
}
public void show2() {
System.out.println(this.x + ", " + this.y);
}
public static long dist2(Vector a, Vector b) {
int dx = abs(a.x - b.x);
int dy = abs(a.y - b.y);
if (dx > 1e8)
throw new IllegalArgumentException("Input is to Large.");
if (dy > 1e8)
throw new IllegalArgumentException("Input is to Large.");
return (dx * dx + dy * dy);
}
}
static class CompVector implements Comparator<Vector> {
public int compare(Vector a, Vector b) {
if (a.x == b.x)
return a.y - b.y;
else
return a.x - b.x;
}
}
static class CompLVector implements Comparator<LVector> {
public int compare(LVector a, LVector b) {
if (a.x == b.x)
return getsign(a.y - b.y);
else
return getsign(a.x - b.x);
}
}
static class FastScanner {
//@Japanese ネットから拾ってきた。よく分からんし、著作権侵害
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nexL() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b) || b == ':') {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nexI() {
long nl = nexL();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
throw new NumberFormatException();
}
return (int) nl;
}
public double nexD() {
return Double.parseDouble(next());
}
public int[] ai(int ln) {
int[] as = new int[ln];
for (int i = 0; i < ln; i++) {
as[i]=nexI();
}
return as;
}
public long[] al(int ln) {
long[] as = new long[ln];
for (int i = 0; i < ln; i++) {
as[i]=nexL();
}
return as;
}
// a means array
public void ai(int[]... array) {
for (int i = 0; i < array[0].length; i++) {
for (int j = 0; j < array.length; j++) {
array[j][i] = nexI();
}
}
return;
}
public void al(long[]... array) {
for (int i = 0; i < array[0].length; i++) {
for (int j = 0; j < array.length; j++) {
array[j][i] = nexL();
}
}
return;
}
public void aimin1(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = nexI() - 1;
}
return;
}
public void aD(double[]... array) {
for (int i = 0; i < array[0].length; i++) {
for (int j = 0; j < array.length; j++) {
array[j][i] = nexD();
}
}
return;
}
public void ai2d(int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
array[i][j] = nexI();
}
}
return;
}
public void al2d(long[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
array[i][j] = nexL();
}
}
return;
}
}
}
// END OF THE CODE