import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;



class Solution {


static int DataLen;

static String[][] map;

static boolean Debug = false;


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


BufferedReader br;

if(Debug) {

File f = new File("C:\\Users\\wvimi\\eclipse-workspace\\HelloWorld2\\input", "input (0).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

}else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

DataLen = Integer.parseInt(br.readLine());

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


// 입력부

StringTokenizer st; 

map = new String[DataLen][];

for (int i = 0; i < DataLen; i++) {

map[i] = new String[DataLen];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < DataLen; j++) {

map[i][j] = st.nextToken();

}

}


// 실행부

String result = "";

int y, x, num;

for (int i = 0; i < CommandLen; i++) {

st = new StringTokenizer(br.readLine());

y = Integer.parseInt(st.nextToken()) -1;

x = Integer.parseInt(st.nextToken()) -1;

num = Integer.parseInt(st.nextToken());

Amount = 0;

goPath(y,x, num);

result = String.format("#%d %d", i+1, Amount);

System.out.println(result);

}


}


static int rotX[] = { 1, 0, -1, 0 };

static int rotY[] = { 0, 1, 0, -1 };

static int Amount;

static private void goPath(int y, int x, int num) {

if(num==0) {

Amount = (map[y][x].charAt(1) - '0') * 1000 ;

return;

}


int move_len = map[y][x].charAt(1) - '0'; // 거리

int rot; // 방위

switch (map[y][x].charAt(0)) {

case 'E': // +x

rot = 0;

break;

case 'W': // -x

rot = 2;

break;

case 'S': // y+

rot = 1;

break;

case 'N': // y-

rot = 3;

break;

default: // input case Error

rot = -1; 

}

int move_y = y + move_len* rotY[rot];

int move_x = x + move_len* rotX[rot];

if(isRight(move_y, move_x)) {

goPath(move_y, move_x, num-1);

}else {

Amount = 10000;

}

}


static private boolean isRight(int y, int x) {

if (x < 0 || x > DataLen - 1 || y < 0 || y > DataLen - 1) {

return false;

}


return true;

}


private static void log(String input) {

if (true) {

System.out.println(input);

}

}


}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;


class Solution {


static int knum, depth, Width;

static int[][] data;

static boolean Converse;

private static int Result;

private static boolean Debug = false;


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


BufferedReader br;

br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st;

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

for (int T = 1; T <= TestNo; T++) {

st = new StringTokenizer(br.readLine());


// 문제 읽기

depth = Integer.parseInt(st.nextToken());

Width = Integer.parseInt(st.nextToken());

knum = Integer.parseInt(st.nextToken());


data = new int[depth][];

// 데이터 읽기

for (int i = 0; i < depth; i++) {

data[i] = new int[Width];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < Width; j++) {

data[i][j] = Integer.parseInt(st.nextToken());

}

}


Result = -1;

if (isOkay()) { // 원형 그대로 두어도 Okay

Result = 0;

}


for (int i = 1; i <= knum; i++) { // i개의 행에 약물 주입

if (Result >= 0) {

break; // 찾았으면 종료

}


visitingList = new ArrayList<>(); // 중복검색 방지

possibleList = new ArrayList<Integer>(); // 1이 i개인 이진수 탐색


int con_i = i > Width / 2 ? Width - i : i;

Converse = i > Width / 2;


findPossible(con_i, 0); // 1이 i개인 이진수 탐색


for (int j = 0; j < possibleList.size(); j++) {

log(Integer.toBinaryString(possibleList.get(j)));


Result = inputMedi(possibleList.get(j)); // (약물 주입) 행들의 집합을 넘긴다.

if (Result > 0) {

break; // 찾았으면 종료

}


}

}


System.out.println(String.format("#%d %d", T, Result));

}


}




static ArrayList<Integer> possibleList;

static ArrayList<Integer> visitingList;


// width개 중 i개를 선택한다.

private static void findPossible(int i, int bitinfo) {

if (bitinfo >= (1 << depth + 1)) {

return;

}


int count = 0;

for (int j = 0; j < depth; j++) {

if ((bitinfo & (1 << j)) > 0) {

count++;

if (count == i) {

log(Integer.toBinaryString(bitinfo));

possibleList.add(bitinfo);

return;

}

}

}


for (int j = 0; j < depth; j++) {

if ((bitinfo & (1 << j)) > 0) {

continue;

}

int next_bitinfo = bitinfo + (1 << j);

if (visitingList.contains(next_bitinfo)) {

continue;

}

visitingList.add(next_bitinfo);

findPossible(i, next_bitinfo);

}

}


public static int inputMedi(int selbit) {


ArrayList<Integer> pocket = new ArrayList<Integer>();

// 사용되는 열 추출


int con_selbit = selbit;


if (Converse) {

con_selbit = 0;

for (int i = 0; i < Width; i++) {

if ((selbit & (1 << i)) == 0) {

con_selbit += (1 << i);

}

}

}


for (int i = 0; i < Width; i++) {

if ((con_selbit & (1 << i)) > 0) {

pocket.add(i);

}

}


// boolean isFound;

int size = pocket.size();


// 1,0의 적용의 경우의 수

for (int i = 0; i < 1 << size; i++) {

// log(Integer.toBinaryString(i));

if (isOkay(i, pocket)) {

return pocket.size();

}

}


return -1;

}


private static boolean isOkay(int bitmask, ArrayList<Integer> pocket) {


int depth = data.length;

int width = data[0].length;


int a_count;

int b_count;


for (int i = 0; i < width; i++) {

a_count = b_count = 0;

int atom;

for (int j = 0; j < depth; j++) { // 한 열을 검사

atom = data[j][i];

if (pocket.indexOf(j) >= 0) {

boolean isOne = (bitmask & (1 << pocket.indexOf(j))) > 0;

atom = isOne ? 1 : 0;

}


if (atom == 1) {

if (b_count != 0) {

a_count = b_count = 0;

}

a_count++;

} else {

if (a_count != 0) {

a_count = b_count = 0;

}

b_count++;

}

if (a_count == knum || b_count == knum) {

break;

}

if (j == depth - 1) {

return false;

}

}

}


log(Integer.toBinaryString(bitmask) + pocket.toString());

return true;


}


private static boolean isOkay() {

int depth = data.length;

int width = data[0].length;


int a_count;

int b_count;


for (int i = 0; i < width; i++) {

a_count = b_count = 0;

for (int j = 0; j < depth; j++) { // 한 열을 검사

if (data[j][i] == 1) {

if (b_count != 0) {

a_count = b_count = 0;

}

a_count++;

} else {

if (a_count != 0) {

a_count = b_count = 0;

}

b_count++;

}

if (a_count == knum || b_count == knum) {

break;

}

if (j == depth - 1) {

return false;

}

}

}


return true;

}


private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.StringTokenizer;


class Edge {

int start, end;

int weight;


public Edge(int start, int end, int weight) {

this.start = start;

this.end = end;

this.weight = weight;

}

}


class Node<T> extends ArrayList<T> {

public static Node[] Tree;

public int nodeNo;

public int parentNo;

public int rank;


public void makeSet(int x) {

nodeNo = x;

parentNo = x;

rank = 0;

}


public int findSet() {


Stack<Integer> nodeStack = new Stack<>();


nodeStack.add(nodeNo); // 검색 노드 조건

Node moveNode = Tree[nodeNo];

while (moveNode.nodeNo != moveNode.parentNo) { // 부모 노드 조건

moveNode = Tree[moveNode.parentNo];

nodeStack.add(parentNo);

}


if (nodeStack.size() > 1) { // 찾은 부모가 있다면

int represent = moveNode.nodeNo;


while (!nodeStack.isEmpty()) { // 부모노드를 가르키도록

Tree[nodeStack.pop()].parentNo = represent;

}

}


return moveNode.nodeNo;

}


public void unionSet(Node<T> node) {

Node first = Tree[this.nodeNo];

Node second = Tree[node.nodeNo];

int f = first.findSet();

int s = second.findSet();

if (f == s) {

return;

}


first = Tree[f];

second = Tree[s];


if (first.rank > second.rank) {

second.parentNo = first.nodeNo;

} else {

first.parentNo = second.nodeNo;

if (this.rank == node.rank) {

node.rank++;

}

}

}


}


class Solution {


static int DATA_SIZE;

static Node<Edge>[] tree;

static Boolean isFound;

static int[] visited;

static int[] distance;

static boolean Debug = true;


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


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "input (29).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in));

}


StringTokenizer st;

int start, end, weight;

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

for (int T = 1; T <= 6; T++) {

st = new StringTokenizer(br.readLine());

int nodeNum = Integer.parseInt(st.nextToken());

int taskNum = Integer.parseInt(st.nextToken());


StringBuffer sb = new StringBuffer();

System.out.print(String.format("#%d", T, nodeNum, taskNum));

log("");


tree = new Node[nodeNum + 1];

visited = new int[nodeNum + 1];

distance = new int[nodeNum + 1];


Node.Tree = tree;

for (int i = 0; i < tree.length; i++) {

tree[i] = new Node<Edge>();

tree[i].makeSet(i);

}

// [방법2]

ArrayList<Integer> representList = new ArrayList<>();


for (int i = 0; i < taskNum; i++) {

st = new StringTokenizer(br.readLine());

switch (st.nextToken()) {

case "!":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());

weight = Integer.parseInt(st.nextToken());


tree[start].add(new Edge(start, end, weight));

tree[end].add(new Edge(end, start, -1 * weight));

tree[start].unionSet(tree[end]);

break;

case "?":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());


// findPath(start, end);

int a = tree[start].findSet();

int b = tree[end].findSet();

if (a == b) {

// [방법2 ] 무게의 상대값을 기록하여 재활용하기

// if(!representList.contains((Integer) a)) {

// representList.add(a);

// visited = new int[nodeNum + 1];

// distance = new int[nodeNum + 1];

// }

int w_end = findWeight(end);

int w_start = findWeight(start);

int answer = w_end - w_start;


sb.append(String.format(" %d", answer));

} else {

sb.append(" UNKOWN");

}

break;

}

}


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

}


}


private static int findWeight(int nodeNo) {

if (visited[nodeNo] == 1) {

log(String.format("3. distance[%d] = %d", nodeNo, distance[nodeNo]));

return distance[nodeNo];

}


// 연결된 노드를 찾는다.

int subParent = 0;

Queue<Integer> que = new LinkedList();

que.add(nodeNo);

Stack<Integer> visiting = new Stack();


while (!que.isEmpty()) {

int reStart = que.poll();

log(String.format("nodeNo:%d    reStart: %d", nodeNo, reStart));

for (Edge line : tree[reStart]) {

log(String.format("visited[%d] = %d", line.end, visited[line.end]));

if (visited[line.end] == 1 || line.end == tree[nodeNo].parentNo) {

// 무게가 기록된 연결된 노드를 찾음 || 부모노드

subParent = line.end;

break;

}

que.add(line.end);

visited[line.end] = 1;

visiting.add(line.end);

}

}


for (int i : visiting) {

visited[i] = 0;

}

que = new LinkedList();

que.add(subParent);

log("subParent 진입: " + subParent);

while (!que.isEmpty()) {

int reStart = que.poll();

for (Edge line : tree[reStart]) {

if (visited[line.end] == 1) {

continue;

}

// que.add(line.end);

que.add(line.end);

visited[line.end] = 1;

distance[line.end] = distance[line.start] + line.weight;

log(String.format("2. distance[%d] = %d", line.end, distance[line.end]));


if (line.end == nodeNo) {

return distance[line.end];

}

}

}


return -1;

}

private static void log(String input) {

if (true) {

System.out.println(input);

}

}


}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
 
class Solution {
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int T = 1; T <= 10; T++) {
 
            // [input] 데이터 입력
            int dataSize = Integer.parseInt(br.readLine());
            String[] originData = br.readLine().trim().split(" ");
            int commandSize = Integer.parseInt(br.readLine());
            String[] commandData = br.readLine().trim().split(" ");
 
            LinkedList<Integer> ticket = new LinkedList<>();
 
            for (int i = 0; i < originData.length; i++) {
                ticket.add(Integer.parseInt(originData[i]));
            }
 
            int cnt = 0;
            while (cnt < commandData.length) {
                String Command = commandData[cnt++];
                 
                int commandIndex = -1;
                if(!Command.equals("A")) {
                    commandIndex = Integer.parseInt(commandData[cnt++]);
                }
                 
                int Valuecount = Integer.parseInt(commandData[cnt++]);
 
                if(Command.equals("I")) {
                    int insertValue;
                    for (int j = 0; j < Valuecount; j++) {
                        insertValue = Integer.parseInt(commandData[cnt++]);
                        ticket.add(commandIndex++, insertValue);
                    }
                }else if(Command.equals("D")) {
                    for (int j = 0; j < Valuecount; j++) {
                        ticket.remove(commandIndex);
                    }
                }else {
                    int addValue;
                    for (int j = 0; j < Valuecount; j++) {
                        addValue = Integer.parseInt(commandData[cnt++]);
                        ticket.add(addValue);
                    }
                }
                 
            }
 
            String result = String.format("#%d", T);
            for (int i = 0; i < 10; i++) {
                result += String.format(" %d", ticket.get(i));
            }
             
            System.out.println(result);
        }
 
    }
 
}


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
 
class Solution {
 
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int T = 1; T <= 10; T++) {
 
            Stack<Character> operStack = new Stack<>();
            Stack<Character> postStack = new Stack<>();
             
            Stack<Integer> calStack = new Stack<>();
 
            // [input] CaseNo DataLen
            int testLen = Integer.parseInt(br.readLine());
 
            // [input] 데이터 입력 ex. "(3+5+(4+3*6))", "3*2*6*(2+3)+4+1+5*7*8"
            String readLine = br.readLine();
             
            // Part1. 후위연산으로 변환
            for (int i = 0; i < testLen; i++) {
                char input = readLine.charAt(i);
                 
                if(input == '(') {
                    operStack.push(input);
                }else if(input == ')') {
                    while(operStack.peek()!='(') { // 연산자 스택에는 괄호가 pair로 존재
                        // 괄호 안에 연산자가 남아있는 연산자 처리 (우선순위가 높은 연산자, 혹
                        postStack.push(operStack.pop());
                    }
                    operStack.pop(); // ( ) 까지 연산을 끝냈으므로  '('을 날림
                }else if(input >= '0' && input <='9') {
                    postStack.push(input);
                }else {
                    // 연산자가 2번 연달아오기 직전 5 + 6 * 7 + 8
                    // post: [5,6,7] oper: [+,*] input:'+' => post: [5,6,7,*,+] oper[+]
                     
                    // case1(While 통과). 우선순위가 낮거나 같은 연산자가 온 경우, 연산자 스택의 pop하여 후위연산 배열에 넣는다.
                    while(!operStack.isEmpty() && priority(input) >= priority(operStack.peek())) {
                        postStack.push(operStack.pop());
                        if(operStack.isEmpty()) {
                            break;
                        }
                    }
                    // case2(While 무시). 우선순위가 높은 연산자가 input으로 왔을 때는, 연산자스택의 값을 pop하지 않는다.
                     
                    operStack.push(input); // 최근 연산자는 스택에 저장
                }
            }
             
            // 괄호가 없는 input 값이 주어졌다면, 마지막에 스택에는 마지막 연산자가 남아있다.
            while(!operStack.isEmpty()) {
                postStack.push(operStack.pop());
            }
             
             
            // Part2. 계산과정
            int x,y;
            int length = postStack.size();
            Character[] postArr = new Character[length];
            postStack.toArray(postArr);
             
            for(int i=0; i<length; i++) {
                char item = postArr[i];
                // System.out.print(item); 후위연산 변환 디버깅
                if(item >= '0' && item <= '9') {
                    calStack.push(item-'0');
                }else if(item == '*') {
                    x = calStack.pop();
                    y = calStack.pop();
                    calStack.push(x*y);
                }else if(item == '+') {
                    x = calStack.pop();
                    y = calStack.pop();
                    calStack.push(x+y);
                }
            }
 
            System.out.println(String.format("#%d %d", T, calStack.pop()));
        }
 
    }
 
    // 연산자 우선 순위 (값이 낮을 수록 우선순위가 높다)
     
    private static int priority(char c) {
        switch(c) {
        case '(':   return 5; // 괄호가 로직에 영향을 주지 않도록 큰 값을 부여
        case '*':   return 1;
        case '-':   return 2
        case '+':   return 2;
        default : return -1;
        }
    }
 
}


import java.util.Scanner;
import java.util.Stack;
 
class Solution {
 
    public static void main(String args[]) throws Exception {
 
        Scanner sc = new Scanner(System.in);
        int[] pair = new int[256]; // 아스키코드
         
        pair['('] = ')';
        pair['['] = ']';
        pair['{'] = '}';
        pair['<'] = '>';
         
        for (int T = 1; T <= 10; T++) {
 
            Stack<Character> stack = new Stack();
            boolean possible = true;
 
            // [input] Test 번호
            int inputLen = Integer.parseInt(sc.nextLine());
             
            // [input] 데이터 입력 & 풀이
            String line = sc.nextLine();
            for (int i = 0; i < inputLen; i++) {
                 
                char input = line.charAt(i);
                // 괄호시작