Player.java

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

class Glb {
	static boolean DEBUG = false;
	static int COMMENT_MODE = 2;
	static boolean GC_PER_TURN = false;
	
	static final int COLS = 13;
	static final int ROWS = 11;
	static final int PLAYER_NUM = 4;
	static final int BOMB_TIMER = 8;
	static final int ITEM_RANGE = 1;
	static final int ITEM_BOMB = 2;
	
	static int myID;
	static int initialPlayerNum;
	static int initialBoxNum;
	static boolean nearBoxBonus = false;
	static int chokudaiIterationCount;
}
class Util {
	static final int[] D = {1,0,-1,0,0,0};
	static boolean isBox(char c) {
		return '0' <= c && c <= '9';
	}
	static boolean rangeCheck(int i,int j) {
		return i >= 0 && i < Glb.ROWS && j >= 0 && j < Glb.COLS;
	}
	static char[][] copy2D(char[][] map) {
		char[][] map2 = new char[Glb.ROWS][];
		for(int i=0;i<Glb.ROWS;i++) map2[i] = Arrays.copyOf(map[i], Glb.COLS);
		return map2;
	}
	static boolean[][] copy2D(boolean[][] map) {
		boolean[][] map2 = new boolean[Glb.ROWS][];
		for(int i=0;i<Glb.ROWS;i++) map2[i] = Arrays.copyOf(map[i], Glb.COLS);
		return map2;
	}
	static int dist(int i1,int j1,int i2,int j2) {
		return Math.abs(i1 - i2) + Math.abs(j1 - j2);
	}
	static void printMap(PrintStream os, char[][] m) {
		for(int i=0;i<m.length;i++) {
			os.println(m[i]);
		}
	}
	static String fizzbuzz(int n) {
		if (n % 15 == 0) return "FizzBuzz";
		if (n % 3 == 0) return "Fizz";
		if (n % 5 == 0) return "Buzz";
		return String.valueOf(n);
	}
	static void debug(Object o) {
		if (Glb.DEBUG) {
			System.err.println(o);
		}
	}
}
class Player {
	public static void main(String[] args) {
		new Player().aiMain();
	}
	
	FastScanner sc = new FastScanner();

	int turn = 0;
	
	public void aiMain() {
		Hash.init();
		
		sc.nextInt(); //13
		sc.nextInt(); //11
		Glb.myID = sc.nextInt();
		
		while(true) {
			turn++;
			input();
			if (turn == 1) init();
			long sTime = System.nanoTime();
			String move = ai0();
			if (Glb.GC_PER_TURN) {
				if ((System.nanoTime() - sTime) / 1000 > 20_000) {
					System.gc();
				}
			}
			double thinkTimeMS = (System.nanoTime() - sTime) / 1000000D;
			String comment;
			if (Glb.COMMENT_MODE == 1) {
				comment = " " + Util.fizzbuzz(turn);
			}else if(Glb.COMMENT_MODE == 2) {
				comment = String.format(" %.3fms %dItr",thinkTimeMS,Glb.chokudaiIterationCount);
			}else{
				comment = "";
			}
			Util.debug(String.format("%.3fms", thinkTimeMS));
			System.out.println(move + comment);
		}
	}
	
	char[][] map;
	ArrayList<Bomber> bomber;
	Bomber[] bomberArray;
	Bomber me;
	ArrayList<Bomb> bomb;
	ArrayList<Item> item;
	
	void init() {
		Glb.initialPlayerNum = bomber.size();
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (Util.isBox(map[i][j])) {
					Glb.initialBoxNum++;
				}
			}
		}
		
		if (Glb.initialPlayerNum >= 3) {
			Glb.nearBoxBonus = true;
		}
	}
	
	void input() {
		StringBuilder echo = new StringBuilder();
		
		map = sc.nextCharMap(Glb.ROWS, Glb.COLS);
		for(int i=0;i<Glb.ROWS;i++) {
			echo.append(map[i]);
			echo.append('\n');
		}
		
		bomber = new ArrayList<>();
		bomberArray = new Bomber[4];
		bomb = new ArrayList<>();
		item = new ArrayList<>();
		
		int entityNum = sc.nextInt();
		echo.append(entityNum);
		echo.append('\n');
		for(int i=0;i<entityNum;i++) {
			int type = sc.nextInt();
			int owner = sc.nextInt();
			int posJ = sc.nextInt();
			int posI = sc.nextInt();
			int param1 = sc.nextInt();
			int param2 = sc.nextInt();
			if (type == 0) {
				Bomber b = new Bomber(posI, posJ, owner, param1, param2);
				if (owner == Glb.myID) {
					me = b;
				}
				bomber.add(b);
				bomberArray[owner] = b;
			}else if(type == 1) {
				bomb.add(new Bomb(posI, posJ, owner, param1, param2));
			}else if(type == 2) {
				item.add(new Item(posI, posJ, param1));
			}
			echo.append(type + " " + owner + " " + posJ + " " + posI + " " + param1 + " " + param2 + "\n");
		}
		
		Util.debug(echo.toString());
	}
	
	String ai0() {
		BoardCache.clear();
		Glb.chokudaiIterationCount = 0;
		
		boolean noBox = true;
		LOOP: for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (Util.isBox(map[i][j])) {
					noBox = false;
					break LOOP;
				}
			}
		}
		
		Board input = new Board(map, item, bomb, null);
		Pair<Board,SimBombResult> p = BoardCache.simAll(input);
		if (p.second.explosionMap[me.i][me.j]) {
			Util.debug("KABOOOOOOM");
			return "BOMB " + me.j + " " + me.i;
		}
		
		Me me2 = new Me(me.i, me.j, me.bombLeft, me.bombLeft + input.countBomb(Glb.myID), me.bombRange);
		

		
		ArrayList<Node> al = null;
		
		int searchDepth;
		if (noBox) {
			searchDepth = 9;
			al = considerEnemyBomb(p.first, me2, searchDepth, 0, 1, 50_000);
		}else{
			searchDepth = 14;
			al = considerEnemyBomb(p.first, me2, searchDepth, 5, 1, 70_000);
		}
		
		if (al == null || al.get(al.size()-1).turn < searchDepth) {
			Util.debug("Danger!");
			Node firstNode = new Node(null, null, p.first, 0, me2, 0);
			al = chokudaiSearchAI(firstNode,9,0,1,5_000);
		}
		
		if (Glb.DEBUG) {
			Util.debug(al.get(al.size()-1));
			StringBuilder sb = new StringBuilder();
			for(int i=0;i<al.size()-1;i++) {
				Move mv = al.get(i).lastMove;
				if (mv != null) {
					sb.append(mv + ", ");
				}
			}
			Util.debug(sb.toString());
		}
		
		Move mv = al.size() <= 1 ? null : al.get(1).lastMove;
		if (mv == null) {
			Util.debug("STUCK!?");
			return "BOMB " + me.j + " " + me.i;
		}else{
			String cmd = mv.bomb ? "BOMB" : "MOVE";
			return cmd + " " + (me.j + Util.D[mv.dir^1]) + " " + (me.i + Util.D[mv.dir]);
		}
	}
	
	ArrayList<Node> considerEnemyBomb(Board b, Me me2, int beamDepth, int bombTurn, int chokudaiWidth, long timeLimitUS) {
		Board enemyBombed = b.copyAll();
		for(Bomber bb: bomber) {
			if (bb.id != Glb.myID && bb.bombLeft > 0) {
				enemyBombed.bomb.add(new Bomb(bb.i, bb.j, bb.id, Glb.BOMB_TIMER, bb.bombRange));
			}
		}
		
		Node firstNodeB = new Node(null, null, enemyBombed, 0, me2, 0);
		
		ArrayList<Node> al = chokudaiSearchAI(firstNodeB,beamDepth,bombTurn,chokudaiWidth,timeLimitUS);
		
		if (al.size() <= 1 || al.get(1).lastMove == null) {
			return null;
		}
		
		return al;
	}
	
	ArrayList<Node> chokudaiSearchAI(Node firstNode, int beamDepth, int bombTurn, int chokudaiWidth, long timeLimitUS) {
		long sTime = System.nanoTime();
		
		@SuppressWarnings("unchecked")
		PriorityQueue<Node>[] beam = new PriorityQueue[beamDepth+1];
		@SuppressWarnings("unchecked")
		HashSet<Integer>[] hs = new HashSet[beamDepth+1];
		Node[] best = new Node[beamDepth+1];
		for(int i=0;i<=beamDepth;i++) {
			beam[i] = new PriorityQueue<>(Collections.reverseOrder());
			hs[i] = new HashSet<>();
		}
		beam[0].add(firstNode);
		best[0] = firstNode;
		while((System.nanoTime() - sTime) / 1000 <= timeLimitUS) {
			for(int t=0;t<beamDepth;t++) {
				for(int i=0;i<chokudaiWidth;i++) {
					if (beam[t].isEmpty()) break;
					Node cur = beam[t].poll();
					for(Node next: neighbor(cur, t < bombTurn)) {
						if (hs[t+1].contains(next.hashCode())) {
							continue;
						}
						Evaluator.evaluate(this,next);
						if (best[t+1] == null || best[t+1].score < next.score) {
							best[t+1] = next;
						}
						beam[t+1].add(next);
					}
				}
			}
			Glb.chokudaiIterationCount++;
		}
		Node cur = null;
		for(int i=beamDepth;i>=0;i--) {
			if ((cur = best[i]) != null) {
				break;
			}
		}
		
		ArrayList<Node> nodes = new ArrayList<>();
		while(cur != firstNode) {
			nodes.add(cur);
			cur = cur.before;
		}
		nodes.add(cur);
		Collections.reverse(nodes);
		
		return nodes;
	}
	ArrayList<Node> neighbor(Node c, boolean bomb) {
		if (c.me.bombLeft == 0) bomb = false;
		
		ArrayList<Node> ret = new ArrayList<>();
		
		Pair<Board,SimBombResult> defaultNext = BoardCache.simAll(c.b);
		for(int k=0;k<5;k++) {
			Node n = move(c, defaultNext, k, false);
			if (n != null) ret.add(n);
			
			if (bomb) {
				n = move(c, defaultNext, k, true);
				if (n != null) ret.add(n);
			}
		}
		
		return ret;
	}
	
	Node move(Node c, Pair<Board,SimBombResult> defaultNext, int dir, boolean bomb) {
		Board b = c.b;
		int ni = c.me.i + Util.D[dir];
		int nj = c.me.j + Util.D[dir^1];
		if (!Util.rangeCheck(ni, nj)) return null;
		if (dir != 4 && !b.before.canMove(ni, nj)) {
			return null;
		}
		if (bomb && dir == 4 && b.before.isBomb(ni, nj)) {
			return null; //爆弾の上に爆弾を置こうとした場合(そんなのある？)
		}
		
		Pair<Board,SimBombResult> next = defaultNext;
		Item take = b.before.getItem(ni, nj);

		if (bomb || take != null) {
			b = b.copyAll();
			if (take != null) {
				b.item.remove(take);
			}
			if (bomb) {
				b.bomb.add(new Bomb(c.me.i, c.me.j, Glb.myID, Glb.BOMB_TIMER, c.me.bombRange));
			}
			next = BoardCache.simAll(b);
		}
		
		if (next.second.explosionMap[ni][nj]) {
			return null;
		}
		
		int bombMax = c.me.bombMax;
		int bombRange = c.me.bombRange;
		if (take != null) {
			if (take.type == Glb.ITEM_RANGE) {
				bombRange++;
			}else{
				bombMax++;
			}
		}
		
		Me me2 = new Me(ni, nj, bombMax - b.countBomb(Glb.myID), bombMax, bombRange);
		return new Node(c, new Move(dir, bomb), next.first, c.turn + 1, me2 , c.boxDestroyed + next.second.boxesDestoryed[Glb.myID]);
	}
}
class Evaluator {
	static final double[] bombScoreTable = {0.0,100.0,300.0,450.0};
	static void evaluate(Player pl, Node n) {
		int boxDestroying = 0;
		Board b = n.b;
		for(int i=0;i<Glb.BOMB_TIMER;i++) {
			Pair<Board,SimBombResult> p = BoardCache.simAll(b);
			boxDestroying += p.second.boxesDestoryed[Glb.myID];
			b = p.first;
		}
		n.boxDestroying = boxDestroying;
		double score = 0;
		double permanentScore = n.before.permanentScore;
		score += n.boxDestroyed * 150.0;
		score += n.boxDestroying * 100.0;
		double bombMaxScore;
		int bn = n.me.bombMax;
		if (bn <= 3) {
			bombMaxScore = bombScoreTable[bn];
		}else{
			bombMaxScore = bombScoreTable[3] + (bn - 3) * 100.0;
		}
		score += bombMaxScore;
		score += n.me.bombRange * 50.0;
		
		permanentScore += n.boxDestroyed * 4.0;
		permanentScore += n.me.bombMax * 2.0;
		permanentScore += n.me.bombRange * 1.0;
		
		int minDist = 999;
		int nearBoxes = 0;
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (Util.isBox(b.map[i][j])) {
					int dist = Util.dist(i, j, n.me.i, n.me.j);
					if (Glb.nearBoxBonus) {
						for(Bomber bb: pl.bomber) {
							if (bb.id == Glb.myID) continue;
							if (dist < Util.dist(i, j, bb.i, bb.j) - n.turn) {
								nearBoxes++;
							}
						}
					}

					minDist = Math.min(minDist, dist);
					
				}
			}
		}
		if (minDist >= 999) {
			minDist = Util.dist(n.me.i, n.me.j, Glb.ROWS / 2 - 1, Glb.COLS / 2);
		}
		score -= minDist * 1.0;
		score += nearBoxes * 0.5;
		score += Math.random() * 0.01;
		
		if (n.turn == 1) {
			//敵が居た所を避ける
			boolean stick = false;
			for(Bomber bb: pl.bomber) {
				if (bb.id == Glb.myID) continue;
				if (bb.i == n.me.i && bb.j == n.me.j) {
					stick = true;
					break;
				}
			}
			if (stick) {
				permanentScore -= 500.0;
			}
		}
		
		n.score = score;
		n.permanentScore = permanentScore;
	}
}
class Node implements Comparable<Node> {
	int turn;
	Node before;
	Move lastMove;
	Board b;
	Me me;
	int boxDestroyed;
	int boxDestroying;
	double score;
	double permanentScore;
	public Node(Node before, Move lastMove, Board b, int turn, Me me, int boxDestroyed) {
		super();
		this.before = before;
		this.lastMove = lastMove;
		this.b = b;
		this.turn = turn;
		this.me = me;
		this.boxDestroyed = boxDestroyed;
	}
	public double score() {
		return score + permanentScore;
	}
	
	@Override
	public int compareTo(Node o) {
		return Double.compare(score(), o.score());
	}
	
	public int hashCode() {
		int h = 0;
		h ^= b.hashCode();
		h ^= Hash.me[me.i][me.j];
		return h;
	}
	
	public String toString() {
		String s = String.format("%.2f", permanentScore);
		if (permanentScore >= 0) s = "+" + s;
		return turn + "T " + boxDestroyed + "+" + boxDestroying + ":火" + me.bombRange + "数" + me.bombMax + ":" + String.format("%.2f",score) + s;
	}
}
class Board {
	char[][] map;
	ArrayList<Item> item;
	ArrayList<Bomb> bomb;
	Board2 before;
	
	public Board(char[][] map, ArrayList<Item> item, ArrayList<Bomb> bomb, Board2 before) {
		super();
		this.map = map;
		this.item = item;
		this.bomb = bomb;
		this.before = before;
	}

	Board copyAll() {
		char[][] map2 = Util.copy2D(map);
		ArrayList<Item> item2 = new ArrayList<>(item);
		ArrayList<Bomb> bomb2 = new ArrayList<>(bomb);
		return new Board(map2, item2, bomb2, before);
	}
	
	SimBombResult simBomb() {
		int n = bomb.size();
		boolean[] ignited = new boolean[n];
		Queue<Integer> q = new ArrayDeque<>();
		for(int i=0;i<n;i++) {
			Bomb b = bomb.get(i);
			if (b.count <= 1) {
				ignited[i] = true;
				q.offer(i);
			}
		}
		int[][] destroyedBy = new int[Glb.ROWS][Glb.COLS];
		boolean[][] explosionMap = new boolean[Glb.ROWS][Glb.COLS];
		boolean[][] willDestroyed2 = new boolean[Glb.ROWS][Glb.COLS];
		
		while(!q.isEmpty()) {
			int c = q.poll();
			Bomb b = bomb.get(c);
			for(int k=0;k<4;k++) {
				LOOP: for(int i=0;i<b.power;i++) {
					int ci = b.i + Util.D[k] * i;
					int cj = b.j + Util.D[k^1] * i;
					if (!Util.rangeCheck(ci, cj)) {
						break;
					}
					if (map[ci][cj] != '.') {
						if (Util.isBox(map[ci][cj])) {
							explosionMap[ci][cj] = true;
							destroyedBy[ci][cj] |= 1 << b.owner;
						}
						break;
					}
					explosionMap[ci][cj] = true;
					boolean blockedByBomb = false;
					for(int j=0;j<n;j++) {
						Bomb b2 = bomb.get(j);
						if (!ignited[j] && ci == b2.i && cj == b2.j) {
							ignited[j] = true;
							q.offer(j);
							blockedByBomb = true;
						}
					}
					if (i != 0 && blockedByBomb) break;
					for(Item it: item) {
						if (it.i == ci && it.j == cj) {
							willDestroyed2[ci][cj] = true;
							break LOOP;
						}
					}
				}
			}
		}
		
		ArrayList<Bomb> bomb2 = new ArrayList<>();
		for(int i=0;i<n;i++) {
			if (!ignited[i]) {
				Bomb b = bomb.get(i);
				bomb2.add(new Bomb(b.i, b.j, b.owner, b.count - 1, b.power));
			}
		}
		
		int[] boxesDestroyed = new int[Glb.PLAYER_NUM];
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (destroyedBy[i][j] != 0) {
					willDestroyed2[i][j] = true;
				}
				for(int k=0;k<Glb.PLAYER_NUM;k++) {
					if ((destroyedBy[i][j] >>> k & 1) == 1) {
						boxesDestroyed[k]++;
					}
				}
			}
		}
		
		return new SimBombResult(new Board2(map, item, bomb2, willDestroyed2, this), explosionMap, boxesDestroyed);
	}
	
	boolean hashCalculated = false;
	private int hash;
	public int hashCode() {
		if (!hashCalculated) {
			hash = calcHash();
			hashCalculated = true;
		}
		return hash;
	}
	private int calcHash() {
		int h = 0;
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (Util.isBox(map[i][j])) {
					h ^= Hash.box[i][j];
				}
			}
		}
		for(Item it: item) {
			h ^= Hash.item[it.i][it.j];
		}
		for(Bomb b: bomb) {
			int own = b.owner == Glb.myID ? 1 : 0;
			int pow = Math.min(b.power, 12) - 3; //power 3 ~ 12+
			h ^= Hash.bomb[own][b.count - 1][pow][b.i][b.j];
		}
		return h;
	}
	
	int countBomb(int owner) {
		int ret = 0;
		for(Bomb b: bomb) {
			if (b.owner == owner) {
				ret++;
			}
		}
		return ret;
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		char[][] map2 = Util.copy2D(map);
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				char c = map2[i][j];
				if ('1' <= c && c <= '2') {
					map2[i][j] = (char) (c - '1' + 'a');
				}else if(c == '0') {
					map2[i][j] = 'o';
				}else{
					map2[i][j] = map[i][j];
				}
			}
		}
		for(Bomb b: bomb) {
			map2[b.i][b.j] = (char) (b.count + '0');
		}
		for(Item it: item) {
			map2[it.i][it.j] = (char) (it.type - 1 + 'A');
		}
		for(int i=0;i<Glb.ROWS;i++) {
			sb.append(map2[i]);
			sb.append('\n');
		}
		return sb.toString();
	}
}
class Board2 {
	boolean[][] willDestroyed;
	char[][] map;
	ArrayList<Item> item;
	ArrayList<Bomb> bomb;
	Board before;
	
	public Board2(char[][] map, ArrayList<Item> item, ArrayList<Bomb> bomb, boolean[][] willDestroyed,
			Board before) {
		super();
		this.willDestroyed = willDestroyed;
		this.map = map;
		this.item = item;
		this.bomb = bomb;
		this.before = before;
	}

	Board simDestruction() {
		char[][] map2 = Util.copy2D(map);
		
		ArrayList<Item> item2 = new ArrayList<>();
		int n = item.size();
		boolean[] destroyed = new boolean[n];
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				if (willDestroyed[i][j]) {
					if (Util.isBox(map2[i][j])) {
						if (map2[i][j] != '0') {
							item2.add(new Item(i, j, map2[i][j] - '0'));
						}
						map2[i][j] = '.';
					}else{
						for(int k=0;k<n;k++) {
							Item it = item.get(k);
							if (it.i == i && it.j == j) {
								destroyed[k] = true;
								break;
							}
						}
					}
				}
			}
		}
		for(int i=0;i<n;i++) {
			if (!destroyed[i]) {
				item2.add(item.get(i));
			}
		}
		
		return new Board(map2, item2, bomb, this);
	}

	boolean canMove(int i,int j) {
		if (map[i][j] != '.') return false;
		for(Bomb b: bomb) {
			if (i == b.i && j == b.j) {
				return false;
			}
		}
		return true;
	}
	
	Item getItem(int i,int j) {
		for(Item it: item) {
			if (i == it.i && j == it.j) {
				return it;
			}
		}
		return null;
	}
	
	boolean isBomb(int i,int j) {
		for(Bomb b: bomb) {
			if (i == b.i && j == b.j) {
				return true;
			}
		}
		return false;
	}
}
class SimBombResult {
	Board2 board;
	boolean[][] explosionMap;
	int[] boxesDestoryed;
	public SimBombResult(Board2 board, boolean[][] explosionmap, int[] boxesDestoryed) {
		this.board = board;
		this.explosionMap = explosionmap;
		this.boxesDestoryed = boxesDestoryed;
	}
}
class BoardCache {
	private static HashMap<Integer, Pair<Board, Pair<Board, SimBombResult>>> map;
	static void clear() {
		if (map == null) {
			map = new HashMap<>();
		}else{
			map.clear();
		}
	}
	static Pair<Board, SimBombResult> simAll(Board b) {
		int h = b.hashCode();
		Pair<Board, Pair<Board, SimBombResult>> p = map.get(h);
		if (p == null) {
			SimBombResult sbr = b.simBomb();
			Board b2 = sbr.board.simDestruction();
			p = new Pair<>(b,new Pair<>(b2,sbr));
			map.put(h, p);
		}
		return p.second;
	}
}
class Item {
	final int i,j,type;

	public Item(int i, int j, int type) {
		super();
		this.i = i;
		this.j = j;
		this.type = type;
	}
	
}
class Bomb {
	final int i,j,owner,count,power;

	public Bomb(int i, int j, int owner, int count, int power) {
		this.i = i;
		this.j = j;
		this.owner = owner;
		this.count = count;
		this.power = power;
	}
	
	Bomb copy() {
		return new Bomb(i,j,owner,count,power);
	}
	
	public String toString() {
		return "[(" + i + "," + j + ")," + count + "," + power + "]";
	}
}
class Move {
	int dir;
	boolean bomb;
	public Move(int dir, boolean bomb) {
		super();
		this.dir = dir;
		this.bomb = bomb;
	}
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (bomb) sb.append("@");
		sb.append("DRULN".charAt(dir));
		return sb.toString();
	}
}
class Me {
	int i,j,bombLeft,bombMax,bombRange;

	public Me(int i, int j, int bombLeft, int bombMax, int bombRange) {
		this.i = i;
		this.j = j;
		this.bombLeft = bombLeft;
		this.bombMax = bombMax;
		this.bombRange = bombRange;
	}
	
	Me copy() {
		return new Me(i,j,bombLeft,bombMax,bombRange);
	}
}
class Bomber {
	int id,i,j,bombLeft,bombRange;

	public Bomber(int i, int j, int id, int bombLeft, int power) {
		super();
		this.id = id;
		this.i = i;
		this.j = j;
		this.bombLeft = bombLeft;
		this.bombRange = power;
	}
}
class Hash {
	static int[][] box = new int[Glb.ROWS][Glb.COLS];
	static int[][] item = new int[Glb.ROWS][Glb.COLS];
	static int[][] me = new int[Glb.ROWS][Glb.COLS];
	static int[][][][][] bomb = new int[2][8][10][Glb.ROWS][Glb.COLS];
	static void init() {
		Random rng = new Random();
		fill2D(rng, box);
		fill2D(rng, item);
		fill2D(rng, me);
		for(int i=0;i<2;i++) {
			for(int j=0;j<8;j++) {
				for(int k=0;k<10;k++) {
					fill2D(rng, bomb[i][j][k]);
				}
			}
		}
	}
	private static void fill2D(Random rng, int[][] a) {
		for(int i=0;i<Glb.ROWS;i++) {
			for(int j=0;j<Glb.COLS;j++) {
				a[i][j] = rng.nextInt();
			}
		}
	}
}
class Pair<A,B> {
	A first; B second;

	public Pair(A first, B second) {
		super();
		this.first = first;
		this.second = second;
	}
	
	public String toString() {
		return "[\n" + first + ",\n" + second + "]";
	}
}
class FastScanner {
	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;}
	private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public boolean hasNextLine() { while(hasNextByte() && isNewLine(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 char[] nextCharArray(int len) {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		char[] s = new char[len];
		int i = 0;
		int b = readByte();
		while(isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}
	public 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();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
	public void close() {try {in.close();} catch (IOException e) {}}
}