ARC082 E - ConvexScore
解法
解説の通りにやった。
の意味するところを考える。これは凸包が S となるような部分集合の数である。
よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいので、全ての部分集合から、凸包が正の面積とならない部分集合を除けば良い。
コード
use std::io; use std::str; use std::usize; use std::cmp; fn mod_pow(x: i64, mut exp: i64, modulo: i64) -> i64 { let mut result = 1; let mut cur = x; while exp > 0 { if exp & 1 == 1 { result = (result * cur) % modulo; } cur = (cur * cur) % modulo; exp >>= 1; } result } fn main() { let modulo = 998244353; let n = read_values::<usize>()[0]; let (x, y) = { let mut x = vec![0; n]; let mut y = vec![0; n]; for i in 0..n { let v = read_values::<i64>(); x[i] = v[0]; y[i] = v[1]; } (x, y) }; let mut ans = mod_pow(2, n as i64, modulo); ans -= 1; ans -= n as i64; ans = (ans + modulo) % modulo; // 両端がそれぞれ i, j となるような線分に乗っている点の数を数える for i in 0..n { for j in (i + 1)..n { let dx = x[i] - x[j]; let dy = y[i] - y[j]; let mut count = 0; let mut left = i; let mut right = j; for k in 0..n { let kx = x[i] - x[k]; let ky = y[i] - y[k]; if dx * ky - kx * dy == 0 { left = cmp::min(left, k); right = cmp::max(right, k); count += 1; } } // 両端が i, j でない時はスルー if left != i || right != j { continue; } // 凸包の面積が 0 であるような部分集合のサイズ let subset = mod_pow(2, count, modulo) - count - 1; ans = (ans + modulo - subset) % modulo; } } println!("{}", ans); } fn read_line() -> String { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }
ARC080 E - Young Maids
Rust の練習
解法
逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i, j の中で が最小になり、かつ、その中で が最小になるような i, j を決めることで、先頭の 2 つは決まる。
このような が最後に残るためには、 のいずれかを満たす が全て取り除かれている必要があるが、隣り合っている数を取り除くため、これらの各区間の中で独立に取り除くことになる。
よって、解法としては、
コード
use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use std::usize; use std::cmp; use std::fmt::Debug; use std::i64::MAX; use std::collections::BinaryHeap; use std::cmp::Ordering; #[derive(Debug, Copy, Clone, Eq, PartialEq)] struct Candidate { minimum: i64, from: usize, until: usize, } impl Ord for Candidate { fn cmp(&self, other: &Candidate) -> Ordering { other.minimum.cmp(&self.minimum) } } impl PartialOrd for Candidate { fn partial_cmp(&self, other: &Candidate) -> Option<Ordering> { Some(self.cmp(other)) } } fn main() { let mut sc = Scanner::new(); let n = sc.parse::<usize>(); let arr = (0..n).map(|_| { sc.parse::<i64>() - 1 }).collect::<Vec<_>>(); let mut rev = vec![0; n]; for i in 0..n { rev[arr[i] as usize] = i; } let mut even_rmq = RangeMinimumQuery::new(n); let mut odd_rmq = RangeMinimumQuery::new(n); for i in 0..n { if i % 2 == 0 { even_rmq.update(i, arr[i]); } else { odd_rmq.update(i, arr[i]); } } let mut ans = Vec::new(); let mut heap = BinaryHeap::new(); heap.push(Candidate { minimum: 0, from: 0, until: n }); while !heap.is_empty() { let s: Candidate = heap.pop().unwrap(); let from = s.from; let until = s.until; let (head, tail) = { let (ref rmq1, ref rmq2) = if from % 2 == 0 { (&even_rmq, &odd_rmq) } else { (&odd_rmq, &even_rmq) }; let minimum_value = rmq1.query(from, until); let minimum_index = rev[minimum_value as usize]; let pair = rmq2.query(minimum_index + 1, until); let pair_index = rev[pair as usize]; (minimum_index, pair_index) }; ans.push(arr[head]); ans.push(arr[tail]); for &(left, right) in &[(from, head), (head + 1, tail), (tail + 1, until)] { if left >= right { continue; } let minimum = if left % 2 == 0 { even_rmq.query(left, right) } else { odd_rmq.query(left, right) }; heap.push(Candidate { minimum: minimum, from: left, until: right }); } } for t in &ans { print!("{} ", t + 1); } println!(); } pub struct RangeMinimumQuery { seg: Vec<i64>, n: usize, } impl RangeMinimumQuery { pub fn new(size: usize) -> RangeMinimumQuery { let mut m = 1; while m <= size { m *= 2; } RangeMinimumQuery { seg: vec![MAX; m * 2], n: m, } } pub fn update(&mut self, mut k: usize, value: i64) { k += self.n - 1; self.seg[k] = value; while k > 0 { k = (k - 1) / 2; self.seg[k] = cmp::min(self.seg[k * 2 + 1], self.seg[k * 2 + 2]); } } /// Get the minimum value in the array in the range [a, b) /// /// # Panics /// /// Panics if `a >= b`. pub fn query(&self, a: usize, b: usize) -> i64 { assert!(a < b); return self.query_range(a, b, 0, 0, self.n); } pub fn query_range(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> i64 { if r <= a || b <= l { return MAX; } if a <= l && r <= b { return self.seg[k]; } let x = self.query_range(a, b, k * 2 + 1, l, (l + r) / 2); let y = self.query_range(a, b, k * 2 + 2, (l + r) / 2, r); cmp::min(x, y) } } struct Scanner { stdin: Stdin, buf: Vec<u8>, } impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), buf: Vec::with_capacity(256), } } fn parse<T: FromStr>(&mut self) -> T where <T as FromStr>::Err: Debug { self.buf.clear(); let mut it = self.stdin.lock().bytes(); let mut c = it.next().unwrap().unwrap(); while c == ' ' as u8 || c == '\n' as u8 { c = it.next().unwrap().unwrap(); } while !(c == ' ' as u8 || c == '\n' as u8) { self.buf.push(c); c = it.next().unwrap().unwrap(); } str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap() } }
CS Academy Round #34 Point in Kgon
復習
コード
import java.util.Scanner; public class Main { private static final int MOD = (int) (1e9 + 7); public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int K = in.nextInt(); long[] x = new long[N * 2]; long[] y = new long[N * 2]; for (int i = 0; i < N; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); } int px = in.nextInt(); int py = in.nextInt(); for (int i = 0; i < N; i++) { x[i] -= px; y[i] -= py; x[i + N] = x[i]; y[i + N] = y[i]; } Combination combination = new Combination(N, MOD); long sum = 0; int bottom = 0; for (int i = 0; i < N; i++) { while (bottom + 1 < N * 2 && x[i] * y[bottom + 1] - y[i] * x[bottom + 1] >= 0) { bottom++; } int count = bottom - i; sum += combination.get(count, K - 1); sum %= MOD; } long ans = (combination.get(N, K) - sum + MOD) % MOD; System.out.println(ans); } static class Combination { private long[] fact; private long[] invFact; private int MOD; public Combination(int max, int MOD) { this.MOD = MOD; long[] inv = new long[max + 1]; fact = new long[max + 1]; invFact = new long[max + 1]; inv[1] = 1; for (int i = 2; i <= max; i++) { inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; } fact[0] = invFact[0] = 1; for (int i = 1; i <= max; i++) { fact[i] = fact[i - 1] * i % MOD; } for (int i = 1; i <= max; i++) { invFact[i] = invFact[i - 1] * inv[i] % MOD; } } public long get(int x, int y) { if (x < y) { return 0; } return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD; } } }
CS Academy Round #36 BBox Count
復習
問題
コード
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main { private static final int MAX = 2500; private static long count(ArrayList<Integer> list, FenwickTree bit) { long ans = 0; int top; int bottom = 0; for (int p : list) { top = p; if (top - bottom >= 2) { ans += choose2Mod(bit.sum(bottom, top)); } bottom = top + 1; } ans += choose2Mod(bit.sum(bottom, MAX)); return ans; } private static long count(ArrayList<Integer> list1, ArrayList<Integer> list2, FenwickTree bit) { long ans = 0; int top; int bottom = 0; for (int i = 0, j = 0; i < list1.size() || j < list2.size(); ) { int p1 = i < list1.size() ? list1.get(i) : MAX; int p2 = j < list2.size() ? list2.get(j) : MAX; int p; if (p1 == p2) { p = p1; i++; j++; } else if (p1 > p2) { p = p2; j++; } else { p = p1; i++; } top = p; if (top - bottom >= 2) { ans += choose2Mod(bit.sum(bottom, top)); } bottom = top + 1; } ans += choose2Mod(bit.sum(bottom, MAX)); return ans; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); ArrayList<Integer>[] points = new ArrayList[MAX]; for (int i = 0; i < MAX; i++) { points[i] = new ArrayList<>(); } for (int i = 0; i < N; i++) { int x = in.nextInt() - 1; int y = in.nextInt() - 1; points[x].add(y); } for (ArrayList<Integer> p : points) { Collections.sort(p); } long ans = 0; boolean[] added = new boolean[MAX]; FenwickTree bit = new FenwickTree(MAX); for (int i = 0; i < MAX; i++) { if (points[i].isEmpty()) { continue; } Arrays.fill(added, false); bit.clear(); for (int j = i; j < MAX; j++) { if (points[j].isEmpty()) { continue; } for (int p : points[j]) { if (!added[p]) { bit.add(p, 1); added[p] = true; } } if (i == j) { continue; } ArrayList<Integer> left = points[i]; ArrayList<Integer> right = points[j]; long total = choose2Mod(bit.sum(0, MAX)); ans += total; ans -= count(left, bit); ans -= count(right, bit); ans += count(left, right, bit); } } System.out.println(ans); } private static long choose2Mod(long x) { return (x * (x - 1) >> 1); } static class FenwickTree { int N; long[] data; FenwickTree(int N) { this.N = N + 1; data = new long[N + 1]; } void clear() { Arrays.fill(data, 0); } void add(int k, long val) { for (int x = k; x < N; x |= x + 1) { data[x] += val; } } // [0, k) long sum(int k) { if (k >= N) { k = N - 1; } long ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += data[x]; } return ret; } // [l, r) long sum(int l, int r) { return sum(r) - sum(l); } } }
CS Academy Round #34 Point in Kgon
コード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { private final int MOD = (int) (1e9 + 7); private final Combination combination = new Combination(400001, MOD); private void solve(FastScanner in, PrintWriter out) { int N = in.nextInt(); int K = in.nextInt(); long[] X = new long[N * 2]; long[] Y = new long[N * 2]; for (int i = 0; i < N; i++) { X[i] = in.nextInt(); Y[i] = in.nextInt(); } int px = in.nextInt(); int py = in.nextInt(); for (int i = 0; i < N; i++) { X[i] -= px; Y[i] -= py; X[i + N] = X[i]; Y[i + N] = Y[i]; } long ans = combination.get(N, K); int right = 0; for (int left = 0; left < N; left++) { right = Math.max(right, left + 1); while (right < left + N && X[left] * Y[right] - Y[left] * X[right] >= 0) { right++; } ans += MOD - combination.get(right - left - 1, K - 1); ans %= MOD; } out.println(ans % MOD); } class Combination { private long[] fact; private long[] invFact; private int MOD; public Combination(int max, int MOD) { this.MOD = MOD; long[] inv = new long[max + 1]; fact = new long[max + 1]; invFact = new long[max + 1]; inv[1] = 1; for (int i = 2; i <= max; i++) { inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; } fact[0] = invFact[0] = 1; for (int i = 1; i <= max; i++) { fact[i] = fact[i - 1] * i % MOD; } for (int i = 1; i <= max; i++) { invFact[i] = invFact[i - 1] * inv[i] % MOD; } } public long get(int x, int y) { if (x < y || y < 0) { return 0; } return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD; } } public static void main(String[] args) { PrintWriter out = new PrintWriter(System.out); new Main().solve(new FastScanner(), out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 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; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } } boolean hasNext() { skipUnprintable(); 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(); } long nextLong() { 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)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = nextInt(); } return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) { array[i] = nextLong(); } return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) { array[i] = next(); } return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) { array[i] = next().toCharArray(); } return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
CS Academy Round #36 BBox Count
コード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.NoSuchElementException; public class Main { private static final int MAX = 2500; // 直線と直線の隙間にある点で作ることが出来る組合せを計算する private long intervalCount(ArrayList<Integer> lines, FenwickTree bit) { long ans = 0; for (int i = -1; i < lines.size(); i++) { int x1 = i >= 0 ? lines.get(i) + 1 : 0; int x2 = i + 1 < lines.size() ? lines.get(i + 1) : MAX; // lines[i] を下辺としたときの上辺の数 // (lines.get(i), x2) if (x2 - x1 >= 2) { // (lines.get(i), lines.get(i+1)) の区間の点を選ぶ組み合わせの数 long k = bit.sum(x1, x2); ans += k * (k - 1) / 2; } } return ans; } private void solve(FastScanner in, PrintWriter out) { int N = in.nextInt(); ArrayList<Integer>[] xs = new ArrayList[MAX]; for (int i = 0; i < MAX; i++) { xs[i] = new ArrayList<>(); } for (int i = 0; i < N; i++) { int y = in.nextInt() - 1; int x = in.nextInt() - 1; xs[y].add(x); } for (ArrayList<Integer> list : xs) { Collections.sort(list); } long ans = 0; for (int left = 0; left < MAX; left++) { if (xs[left].isEmpty()) { continue; } boolean[] added = new boolean[MAX]; FenwickTree bit = new FenwickTree(MAX); int addedCount = 0; for (int right = left; right < MAX; right++) { if (xs[right].isEmpty()) { continue; } for (int x : xs[right]) { if (!added[x]) { added[x] = true; bit.add(x, 1); addedCount++; } } if (right == left) { continue; } // xs[right] と xs[left] をマージしてソートしたリストを作る ArrayList<Integer> merged = new ArrayList<>(xs[left].size() + xs[right].size()); for (int i = 0, j = 0; i < xs[left].size() || j < xs[right].size(); ) { int leftTop = i < xs[left].size() ? xs[left].get(i) : MAX; int rightTop = j < xs[right].size() ? xs[right].get(j) : MAX; if (leftTop == rightTop) { merged.add(leftTop); i++; j++; } else if (leftTop < rightTop) { merged.add(leftTop); i++; } else { merged.add(rightTop); j++; } } // 今あるやつ全部 ans += addedCount * (addedCount - 1) / 2; // right が端点とならないものを全て抜く ans -= intervalCount(xs[left], bit); // left が端点とならないものを全て抜く ans -= intervalCount(xs[right], bit); // right および left が端点とならないもの (重複して引いた分) を足し込む ans += intervalCount(merged, bit); } } out.println(ans); } class FenwickTree { int N; long[] data; FenwickTree(int N) { this.N = N + 1; data = new long[N + 1]; } void add(int k, long val) { for (int x = k; x < N; x |= x + 1) { data[x] += val; } } // [0, k) long sum(int k) { if (k >= N) { k = N - 1; } long ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += data[x]; } return ret; } // [l, r) long sum(int l, int r) { return sum(r) - sum(l); } } public static void main(String[] args) { PrintWriter out = new PrintWriter(System.out); new Main().solve(new FastScanner(), out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 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; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } } boolean hasNext() { skipUnprintable(); 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(); } long nextLong() { 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)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = nextInt(); } return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) { array[i] = nextLong(); } return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) { array[i] = next(); } return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) { array[i] = next().toCharArray(); } return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
AOJ 1163 Cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163
GCD + 二部マッチング
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { private static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } private void solve(FastScanner in, PrintWriter out) { while (true) { int m = in.nextInt(); int n = in.nextInt(); if (m == 0 && n == 0) { break; } int[] b = in.nextIntArray(m); int[] r = in.nextIntArray(n); Dinitz dinitz = new Dinitz(n + m + 2); int source = n + m; int sink = source + 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (gcd(b[i], r[j]) > 1) { dinitz.addEdge(i, j + m, 1); } } } for (int i = 0; i < m; i++) { dinitz.addEdge(source, i, 1); } for (int i = 0; i < n; i++) { dinitz.addEdge(i + m, sink, 1); } out.println(dinitz.maxFlow(source, sink)); } } class Dinitz { class Edge { int to, rev; long cap; Edge(int to, long cap, int rev) { this.to = to; this.cap = cap; this.rev = rev; } } private ArrayDeque<Integer> deque = new ArrayDeque<>(); private ArrayList<ArrayList<Edge>> g; private int[] level; private int[] iter; Dinitz(int V) { g = new ArrayList<>(V); for (int i = 0; i < V; i++) { g.add(new ArrayList<>()); } level = new int[V]; iter = new int[V]; } void addEdge(int from, int to, long cap) { g.get(from).add(new Edge(to, cap, g.get(to).size())); g.get(to).add(new Edge(from, 0, g.get(from).size() - 1)); } private long dfs(int v, int t, long f) { if (v == t) { return f; } for (; iter[v] < g.get(v).size(); iter[v]++) { Edge e = g.get(v).get(iter[v]); if (e.cap > 0 && level[v] < level[e.to]) { long d = dfs(e.to, t, Math.min(f, e.cap)); if (d > 0) { e.cap -= d; g.get(e.to).get(e.rev).cap += d; return d; } } } return 0; } private void bfs(int s) { Arrays.fill(level, -1); level[s] = 0; deque.add(s); while (!deque.isEmpty()) { int v = deque.poll(); for (Edge e : g.get(v)) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; deque.add(e.to); } } } } long maxFlow(int s, int t) { long flow = 0; for (; ; ) { bfs(s); if (level[t] < 0) { return flow; } Arrays.fill(iter, 0); long f; while ((f = dfs(s, t, Long.MAX_VALUE)) > 0) { flow += f; } } } } public static void main(String[] args) { PrintWriter out = new PrintWriter(System.out); new Main().solve(new FastScanner(), out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 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; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } } boolean hasNext() { skipUnprintable(); 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(); } long nextLong() { 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)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = nextInt(); } return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) { array[i] = nextLong(); } return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) { array[i] = next(); } return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) { array[i] = next().toCharArray(); } return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }