kingsubin

import java.io.*;
import java.util.*;
 
public class boj_input {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
 
    // 4 방향
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
 
    // 8 방향
    static int[] dx2 = { 1, 1, 0, -1, -1, -1, 0, 1 };
    static int[] dy2 = { 0, 1, 1, 1, 0, -1, -1, -1 };
 
    // gcd (Greatest Common Divisor)
    static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(a, a % b);
    }
 
    // lcm (Least Common Multiple)
    static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
 
    // Sieve of Eratosthenes
    static void sieveOfEratosthenes(boolean[] prime) {
        for (int i = 2; i*i < prime.length; i++) {
            for (int j = i*2; j < prime.length; j+=i) {
                prime[j] = false;
            }
        }
    }
    
    // next_Permutation
    static boolean next_Permutation(int[] a, int n) {
        int i = n-1;
        while (i > 0 && a[i-1] >= a[i]) i-=1; // 1.
        if (i <= 0) return false; // 마지막 순열
 
        int j = n-1; // 2.
        while (a[j] <= a[i-1]) j-=1;
 
        // 3. swap(a[i-1], a[j]);
        int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;
 
        j = n-1; // 4.
        while (i < j) {
        // swap(a[i], a[j]);
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1; j -= 1;
        }
        return true;
    }
 
    // 2차원 배열 회전
    static int[][] rotate(int turnCount, int[][] sticker) {
        // do turn, turnCount 1 - 90, 2 - 180, 3 - 270 도
        int row = sticker.length;
        int col = sticker[0].length;
        int[][] turnSticker;
 
        // 회전시키기
        if (turnCount == 1) { // 90
            turnSticker = new int[col][row];
            for (int i = 0; i < col; i++) {
                for (int j = 0; j < row; j++) {
                    turnSticker[i][j] = sticker[row-1-j][i];
                }
            }
        } else if (turnCount == 2) { // 180
            turnSticker = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    turnSticker[i][j] = sticker[row-1-i][col-1-j];
                }
            }
        } else { // 270
            turnSticker = new int[col][row];
            for (int i = 0; i < col; i++) {
                for (int j = 0; j < row; j++) {
                    turnSticker[i][j] = sticker[j][col-1-i];
                }
            }
        }
        return turnSticker;
    }
}
 
class Pair {
    int x;
    int y;
 
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}