import java.io.*;
import java.util.*;

public class Main {

    public static int[] arr;
    public static int N,M;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];

        dfs(1,0);
        System.out.println(sb);
    }

    public static void dfs(int at, int depth) {
        if(depth == M) {
            for(int val:arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }

        for(int i=at; i<=N; i++) {
            arr[depth] = i;
            dfs(i+1, depth+1);
        }
    }
}

import java.util.*;
import java.io.*;

public class Main {
    static int N, M, answer;
    static int[] dx = { -1, 0, 1,  0 };
    static int[] dy = {  0, 1, 0, -1 };
    static int[][] map;
    static boolean[][] visited;

    public void DFS(int x, int y, int sum, int L) {
        if (L == 3) {
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextX > N - 1 || nextY < 0 || nextY > M - 1) continue;

            if (!visited[nextX][nextY]) {
                // ㅜ 테트로미노 만들기 위해 1번째 칸에서 탐색을 한 번 더 진행
                if (L == 1) {
                    visited[nextX][nextY] = true;
                    DFS(x, y, sum + map[nextX][nextY], L + 1);
                    visited[nextX][nextY] = false;
                }

                visited[nextX][nextY] = true;
                DFS(nextX, nextY, sum + map[nextX][nextY], L + 1);
                visited[nextX][nextY] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true;
                main.DFS(i, j, map[i][j], 0);
                visited[i][j] = false;
            }
        }

        System.out.println(answer);
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            Queue<Integer> q = new LinkedList<>();
            boolean[] visited = new boolean[10000]; // BFS 탐색의 방문 여부 체크
            String[] command = new String[10000]; // 정답 명령어를 담는 배열


            q.add(a); // a를 큐에 담고
            visited[a] = true; // 방문 표시한다
            Arrays.fill(command,  ""); // 꼭 넣어야하나? 안넣으면 틀림


            while (!q.isEmpty() && !visited[b]) {
                int now = q.poll(); // 큐에서 값을 뺀다 = 현재 탐색 위치

                int D = (2 * now) % 10000; // n을 두배로 바꾸고 10000으로 나눈 나머지
                int S = now == 0 ? 9999 : now - 1; // 0일 때, 9999, 아니면 1을 빼준다 
                int L = (now % 1000) * 10 + now / 1000; // 1234 -> 2341 : 1234를 1000으로 나눈 나머지(234)에 10을 곱함=2340, 1234를 1000으로 나누면 1, 2340+1=2341
                int R = (now % 10) * 1000 + now / 10; // 1234 -> 4123 : 1234를 10으로 나눈 나머지에 1000 곱합 = 4000, 1234를 10으로 나누면 123, 4000+123=4123

                if (!visited[D]) {
                    q.add(D); // 큐에 넣는다
                    visited[D] = true; // 방문처리한다
                    command[D] = command[now] + "D"; // 명령어를 추가한다
                }

                if (!visited[S]) {
                    q.add(S);
                    visited[S] = true;
                    command[S] = command[now] + "S";
                }

                if (!visited[L]) {
                    q.add(L);
                    visited[L] = true;
                    command[L] = command[now] + "L";
                }

                if (!visited[R]) {
                    q.add(R);
                    visited[R] = true;
                    command[R] = command[now] + "R";
                }
            }
            System.out.println(command[b]);
        }
    }
}

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = null;
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(in.readLine());

    for (int tc = 0; tc < T; tc++) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int k = Integer.parseInt(in.readLine());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(in.readLine());

            char c = st.nextToken().charAt(0);
            int n = Integer.parseInt(st.nextToken());

            // n을 트리맵에 삽입
            if (c == 'I') {
                map.put(n, map.getOrDefault(n, 0) + 1);
            }
            // 맵이 비어있는 경우
            else if (map.size() == 0) {
                continue;
            }
            // 최댓값 또는 최솟값 삭제
            else {
                int key = n == 1 ? map.lastKey() : map.firstKey();
                int cnt = map.get(key);

                if (cnt == 1) {
                    map.remove(key);
                } else {
                    map.put(key, cnt - 1);
                }
            }
        }

        if (map.size() == 0) {
            sb.append("EMPTY\n");
        } else {
            sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
        }
    }

    System.out.println(sb.toString());
}
}

import java.io.*;
import java.util.*;
public class Main{
    static int arr[],N,M;
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[101];
        visit = new boolean[101];

        for(int i=0; i<N+M; i++){
            st = new StringTokenizer(br.readLine());
            int x =Integer.parseInt(st.nextToken());
            int y =Integer.parseInt(st.nextToken());
            arr[x]=y;
        }

        bfs(1);
    }
    static void bfs(int start){
        Queue<int[]>q=new LinkedList<>();
        q.add(new int[]{start,0});
        visit[start]=true;

        while(!q.isEmpty()){
            int p[] = q.poll();

            if(p[0]==100){
                System.out.println(p[1]);
                return;
            }

            for(int i=1; i<7; i++){
                int next = p[0]+i;
                if(next<=100){
                    if(arr[next]!=0){
                        next = arr[next];
                    }
                    if(!visit[next]){
                        visit[next] = true;
                        q.add(new int[]{next,p[1]+1});

                    }
                }
            }
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static String S;
    static char[][] arr;
    static boolean[][] visits;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, 1, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new char[N + 1][N + 1];
        visits = new boolean[N + 1][N + 1];

        for (int i = 0; i < N; i++) {
            S = br.readLine(); // RRRBB
            for (int j = 0; j < N; j++) {
                arr[i][j] = S.charAt(j); // R R R B B
            }
        }

        // 정상인 경우
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visits[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        int normal_cnt = cnt;
        cnt = 0;
        visits = new boolean[N + 1][N + 1];

        // 비정상인 경우
        // G를 R로 바꿔주고 돌린다.

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 'G') {
                    arr[i][j] = 'R'; // G를 R로 바꿔준다.
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visits[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        int abnormal_cnt = cnt;
        System.out.println(normal_cnt + " " + abnormal_cnt);

    }

    public static void dfs(int x, int y) {
        visits[x][y] = true;
        char tmp_char = arr[x][y]; // R
        for (int i = 0; i < 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (new_x < 0 || new_y < 0 || new_x > N || new_y > N) {
                continue;
            }

            if (!visits[new_x][new_y] && arr[new_x][new_y] == tmp_char) {
                dfs(new_x, new_y);
            }
        }
    }

}

import java.io.*;
import java.util.*;

public class Main {
    static int N; // 세로 칸의 수
    static int M; // 가로 칸의 수
    static int[][] graph; // 그래프배열
    static boolean[][] visited; //방문한 자리
    static int count = 0; // 최소 날짜
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");


        M = Integer.parseInt(st.nextToken()); // 세로 칸  초기화
        N = Integer.parseInt(st.nextToken()); // 가로 칸 초기화

        // 그래프 초기화
        graph = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 1) { // 1일 경우 큐에 삽입
                    q.add(new int[]{i, j});
                }
            }
        }
        System.out.println(bfs());
    }

    public static int bfs() {
        while (!q.isEmpty()) { // 큐가 다 빌때까지 실행
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            // 4방 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //그래프 범위 안에 있을 경우
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (graph[nx][ny] == 0) {
                        q.add(new int[]{nx, ny});
                        graph[nx][ny] = graph[x][y] + 1; // 새로 추가된 곳은 원래 있던 수 + 1
                        // 그 이유는 날짜를 세기 위해
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 0) { // 그래프안에 0 이 존재하면 답은 -1
                    return -1;
                }
                // 그래프의 날짜중에 가장 큰 수를 찾으면 그것이 최종날짜
                count = Math.max(count, graph[i][j]);
            }
        }

        // 저장될 때부터 모든 토마토가 익어익는상태라면
        if (count == 1) {
            return 0;
        } else { // 아닐 경우 최종날짜 - 1 출력
            return count-1;
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static int M, N, H;
    static int[][][] graph;
    // x, y, z축 이동을 위한 델타 배열 선언
    static int[] dx = {-1, 1, 0, 0, 0, 0};
    static int[] dy = {0, 0, -1, 1, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};
    static Deque<int[]> queue = new ArrayDeque<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        graph = new int[H][N][M];

        // 처음부터 모든 토마토가 익은 상태인지 체크하기 위한 변수 선언
        boolean alreadyFinished = true;

        // 토마토 배열 입력
        for(int k=0; k<H; k++) {
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<M; j++) {
                    graph[k][i][j] = Integer.parseInt(st.nextToken());
                    // 만약 익은 토마토라면 큐에 좌표와 일 수 저장
                    if(graph[k][i][j] == 1) {
                        queue.addLast(new int[]{k, i, j, 0});
                    }
                    // 익지 않은 토마토가 한 개라도 있으면 
                    // BFS를 진행할 수 있으므로 flag값 false로 변경
                    if(graph[k][i][j] == 0) {
                        alreadyFinished = false;
                    }
                }
            }
        }

        // 입력부터 더이상 익힐게 없으면 0 출력 후 종료
        if(alreadyFinished) {
            System.out.println(0);
            return;
        }

        // BFS를 수행하고 반환된 결과값 저장
        int answer = bfs();

        // 익지않은 토마토 체크
        // 있다면 정답을 -1로 변경하고 종료
        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (graph[k][i][j] == 0) {
                        answer = -1;
                        break;
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static int bfs() {
        // 익는데 걸린 일 수를 저장하기 위한 변수 선언
        int day = 0;
        while(!queue.isEmpty()) {
            int[] tmp = queue.removeFirst();
            int z = tmp[0];
            int x = tmp[1];
            int y = tmp[2];
            // 익는데 걸린 일 수 저장
            day = tmp[3];
            for (int i = 0; i < 6; i++) {
                int nz = z + dz[i];
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 범위를 벗어나면 다시 연산
                if (nz < 0 || nx < 0 || ny < 0 || nz >= H || nx >= N || ny >= M) {
                    continue;
                }
                // 익지않은 토마토라면 익히고, 해당 토마토 좌표 및 익는데 걸린 일 수 + 1 큐에 저장
                if (graph[nz][nx][ny] == 0) {
                    graph[nz][nx][ny] = 1;
                    queue.addLast(new int[]{nz, nx, ny, day + 1});
                }
            }
        }
        return day;
    }
}

import java.io.*;
import java.util.*;

public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        ArrayDeque<Integer> deque;
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        while(T --> 0) {

            String command = br.readLine();    // 문제에서 p에 해당하는 명령어
            int n = Integer.parseInt(br.readLine());

            st = new StringTokenizer(br.readLine(), "[],");

            deque = new ArrayDeque<Integer>();

            // 덱에 배열 원소를 넣어준다.
            for(int i = 0; i < n; i++) {
                deque.add(Integer.parseInt(st.nextToken()));
            }

            AC(command, deque);
        }

        System.out.println(sb);

    }

    public static void AC(String command, ArrayDeque<Integer> deque) {

        boolean isRight = true;

        for(char cmd : command.toCharArray()) {

            if(cmd == 'R') {
                isRight = !isRight;    // 방향을 바꿔준다.
                continue;
            }

            // 아래는 D의 경우
            // D 함수이면서 isRight가 true 일 경우
            if(isRight) {
                // 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
                if(deque.pollFirst() == null) {
                    sb.append("error\n");
                    return;
                }
            }
            else {
                // 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
                if(deque.pollLast() == null) {
                    sb.append("error\n");
                    return;
                }    
            }
        }

        // 모든 함수들이 정상적으로 작동했다면 덱의 남은 요소들을 출력문으로 만들어준다.
        makePrintString(deque, isRight);
    }

    public static void makePrintString(ArrayDeque<Integer> deque, boolean isRight) {

        sb.append('[');    // 여는 대괄호 먼저 StringBuilder에 저장

        if(deque.size() > 0) {    //만약 출력 할 원소가 한 개 이상일 경우
            if(isRight) {    // 정방향일경우 
                sb.append(deque.pollFirst());    // 먼저 첫 번째 원소를 넘겨준다.

                // 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 하나씩 뽑아 넘긴다. 
                while(!deque.isEmpty()) {
                    sb.append(',').append(deque.pollFirst());
                }
            }
            else {    // 역방향일경우 
                sb.append(deque.pollLast());    // 먼저 뒤에서부터 첫 번째 원소를 넘겨준다.

                // 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 뒤에서부터 하나씩 뽑아 넘긴다. 
                while(!deque.isEmpty()) {
                    sb.append(',').append(deque.pollLast());
                }
            }
        }

        sb.append(']').append('\n');    // 닫는 대괄호 및 개행으로 마무리
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) { //회의 끝나는 시간이 같다면
                    return o1[0] - o2[0]; //회의 시작 시간 빠른순 정렬
                } else {
                    return o1[1] - o2[1]; //같지 않으면 회의 끝나는 시간 빠른순 정렬
                }
            }
        });

        int cnt = 1; // 하단에 첫번째 회의를 이미 count 함
        int min = arr[0][1]; // 정렬한 배열에서 첫번째 회의 끝나는 시간
        for (int i = 1; i < n; i++) {
            if (arr[i][0] >= min) { // 다음 회의 시작 시간이 회의 첫번째 회의 끝나는 시간보다 크거나 같다면
                min = arr[i][1]; // 회의 끝나는 시간 다시 세팅
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

import java.util.*;

public class Main {

    static int N,r,c,cnt=0;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        r = sc.nextInt();
        c = sc.nextInt();

        find(r,c,(int)Math.pow(2, N));
        System.out.println(cnt);


    }

    static void find(int x,int y, int size) {
        if(size==1)
            return;

        if(x<size/2&&y<size/2) {    //왼쪽 위
            find(x,y,size/2);
        }else if(x<size/2&&size/2<=y) {    //오른쪽 위
            cnt+=(size*size/4);
            find(x,y-size/2,size/2);
        }else if(x>=size/2&&size/2>y) { //왼쪽 아래
            cnt+=(size*size/4)*2;
            find(x-size/2,y,size/2);
        }else {                        //오른쪽 아래
            cnt+=(size*size/4)*3;
            find(x-size/2,y-size/2,size/2);

        }

    }

}

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] result;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        result = new int[n][m];
        int x=0, y=0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) {
                    x = i;
                    y = j;
                } else if (graph[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        bfs(x, y);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    result[i][j] = -1;
                }
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        result[nx][ny] = result[tmp[0]][tmp[1]] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // i에서 j까지 갈 수 있는가?
        // i에서 k로 가고, k에서 j로 갈 수 있는가?
        for (int k = 0; k < n; k++) { // 거쳐갈 노드
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 단순히 갈 수 있는 경로가 있는지만 체크
                    if (map[i][k] == 1 && map[k][j] == 1) {
                        map[i][j] = 1;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }
}

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(Math.abs(o1) > Math.abs(o2)) {
                    return Math.abs(o1) - Math.abs(o2);
                }else if(Math.abs(o1) == Math.abs(o2)) {
                    return o1 - o2;
                }else {
                    return -1;
                }
            }
        });
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            if(x == 0) {
                if(pq.isEmpty()) sb.append("0").append("\n");
                else sb.append(pq.poll()).append("\n");
            }else {
                pq.offer(x);
            }
        }
        System.out.println(sb);
    }

}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for(int t=0; t<T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 최소공배수를 구하기 위해 최대공약수 구하기
            int a = N;
            int b = M;
            int tmp = 0;
            while (b != 0) {
                tmp = b;
                b = a % b;
                a = tmp;
            }

            // 최소공배수
            int lcm = M * N / a;
            int answer = -1;

            // 나머지가 0인 경우를 대비해 나머지가 x-1, y-1인 경우를 탐색
            // x-1 부터 시작해 M씩 더해가며 해답을 도출
            for (int i = x-1; i < lcm + 1; i += M) {
                // (i%M) == x-1 이며(이미 충족), (i%N) == y-1인 i 탐색
                if (i % N == y-1) {
                    answer = i;
                    break;
                }
            }
            // 표현이 가능한 해면 + 1 해서 출력
            // 아니면 -1 출력
            sb.append(answer+1 !=0 ? answer+1 : -1).append('\n');
        }
        System.out.println(sb);

    }
}

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String str = br.readLine();
        int cnt=0, ans=0;

        for(int i=1; i<m-1;){
            if(str.charAt(i)=='O' && str.charAt(i+1)=='I'){
                cnt++;
                if(cnt == n){
                    if(str.charAt(i-(cnt*2-1))=='I')
                        ans ++;
                    cnt--;
                }
                i+=2;
            }
            else {
                cnt=0;
                i++;
            }
        }
        System.out.println(ans);
    }
}

import java.util.*;
import java.io.*;

public class Main {

    static int[][] danji;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static List<Integer> result;
    static int cnt, N;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        result = new LinkedList<>(); 
        N = Integer.parseInt(br.readLine());
        danji = new int[N][N];
        visited = new boolean[N][N]; //단지에 속해있는지
        cnt = 1; //기준이 아파트(단지로 묶일 첫 아파트)가 포함될 때니 1로 초기화

        for(int i=0;i<N;i++) {
            String str = br.readLine();
            for(int j=0;j<N;j++) {
                danji[i][j] = str.charAt(j)-'0';
            }
        }


        for(int x=0;x<N;x++) {
            for(int y=0;y<N;y++) {
                if(danji[x][y]==1 && !visited[x][y]) {
                    dfs(x,y);
                    result.add(cnt);
                    cnt = 1;
                }
            }
        }

        Collections.sort(result);

        bw.write(result.size()+"\n");
        for(int r : result) bw.write(r+"\n");
        bw.flush();
        bw.close();

    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for(int i=0;i<4;i++) {
            int nx = dx[i]+x;
            int ny = dy[i]+y;

            if(nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny] && danji[nx][ny]==1) {
                cnt++;
                dfs(nx,ny);
            }
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {

    static int[][] map;
    static int n;
    static int m;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 }; //x방향배열-상하
    static int[] dy = { 0, 0, -1, 1 }; //y방향배열-좌우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for(int i=0; i<n; i++) {
            String s = br.readLine();
            for(int j=0; j<m; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        visited = new boolean[n][m];
        visited[0][0] = true;
        bfs(0, 0);
        System.out.println(map[n-1][m-1]);
    }

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y});

        while(!q.isEmpty()) {
            int now[] = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i=0; i<4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                        if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
                            continue;
                        if (visited[nextX][nextY] || map[nextX][nextY] == 0)
                            continue;

                        q.add(new int[] {nextX, nextY});
                        map[nextX][nextY] = map[nowX][nowY] + 1;
                        visited[nextX][nextY] = true;
            }
        }
    }
}

import java.io.*;
import java.util.*;

public class Main
{
    static int N;
    static int K;

    static int visited[] = new int[100001];

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        String[] inputs = input.split(" ");

        N = Integer.valueOf(inputs[0]);
        K = Integer.valueOf(inputs[1]);

        int result = bfs(N);
        System.out.println(result);
    }

    private static int  bfs(int node)
    {
        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(node);
        int index = node;
        int n = 0;
        visited[index] = 1;
        while (queue.isEmpty() == false)
        {
            n = queue.remove();

            if (n == K)
            {
                return visited[n]-1;
            }

            if (n-1>=0 && visited[n-1] == 0)
            {
                visited[n-1] = visited[n]+1;
                queue.add(n-1);
            }
            if (n+1 <= 100000 && visited[n+1] == 0)
            {
                visited[n+1] = visited[n]+1;
                queue.add(n+1);
            }
            if (2*n <= 100000 && visited[2*n] == 0)
            {
                visited[2*n] = visited[n] + 1;
                queue.add(2*n);
            }
        }
        return -1;
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());


        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        int KB[] = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            int[] distance = new int[N + 1];
            Arrays.fill(distance, -1);
            distance[i] = 0;
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph.get(current)) {
                    if (distance[next] == -1) {
                        distance[next] = distance[current] + 1;
                        queue.add(next);
                    }
                }
            }
            int sum = 0;
            for (int j = 1; j < N + 1; j++) {
                sum += distance[j];
            }
            KB[i] = sum;
        }

        int min = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i < N + 1; i++) {
            if (KB[i] < min) {
                min = KB[i];
                answer = i;
            }
        }
        System.out.println(answer);
    }
}