AtCoder Regular Contest 089 - GraphXY

AtCoDeer the deer wants a directed graph that satisfies the following conditions:

* The number of vertices, N, is at most 300.
* There must not be self-loops or multiple edges.
* The vertices are numbered from 1 through N.
* Each edge has either an integer weight between 0 and 100 (inclusive), or a label `X` or `Y`.
* For every pair of two integers (x,y) such that 1 ≤ x ≤ A, 1 ≤ y ≤ B, the shortest distance from Vertex S to Vertex T in the graph where the edges labeled `X` have the weight x and the edges labeled `Y` have the weight y, is d_{x,y}.



Construct such a graph (and a pair of S and T) for him, or report that it does not exist. Refer to Output section for output format.

Constraints

* 1 ≤ A,B ≤ 10
* 1 ≤ d_{x,y} ≤ 100 (1 ≤ x ≤ A, 1 ≤ y ≤ B)
* All input values are integers.

Input

Input is given from Standard Input in the following format:


A B
d_{1,1} d_{1,2} .. d_{1,B}
d_{2,1} d_{2,2} .. d_{2,B}
:
d_{A,1} d_{A,2} .. d_{A,B}


Output

If no graph satisfies the condition, print `Impossible`.

If there exists a graph that satisfies the condition, print `Possible` in the first line. Then, in the subsequent lines, print the constructed graph in the following format:


N M
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
S T


Here, M is the number of the edges, and u_i, v_i, c_i represent edges as follows: there is an edge from Vertex u_i to Vertex v_i whose weight or label is c_i.

Also refer to Sample Outputs.

Examples

Input

2 3
1 2 2
1 2 3


Output

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3


Input

1 3
100 50 1


Output

Impossible

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(A, B) = map(int, input().split())
D = [list(map(int, input().split())) for i in range(A)]
N = 101
F = [[0] * N for i in range(N)]
for a in range(N):
	for b in range(N):
		res = 0
		for x in range(A):
			for y in range(B):
				res = max(res, D[x][y] - (x + 1) * a - (y + 1) * b)
		F[a][b] = res
for x in range(A):
	for y in range(B):
		v = 101
		for a in range(N):
			for b in range(N):
				v = min(v, (x + 1) * a + (y + 1) * b + F[a][b])
		if v != D[x][y]:
			print('Impossible')
			exit(0)
print('Possible')
print(2 * N, N ** 2 + 2 * (N - 1))
for i in range(N - 1):
	print(i + 1, i + 2, 'X')
	print(103 + i, 102 + i, 'Y')
for a in range(N):
	for b in range(N):
		print(a + 1, 102 + b, F[a][b])
print(1, 102)


from heapq import *
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def impossible():
	print('Impossible')
	exit()

def main():
	(h, w) = map(int, input().split())
	t = [list(map(int, input().split())) for _ in range(h)]
	edge = [[0] * 101 for _ in range(101)]
	for n_x in range(101):
		for n_y in range(101):
			cost = 0
			for i in range(h):
				for j in range(w):
					(x, y) = (i + 1, j + 1)
					cur_cost = t[i][j] - x * n_x - y * n_y
					if cur_cost > cost:
						cost = cur_cost
			edge[n_x][n_y] = cost
	for i in range(h):
		for j in range(w):
			(x, y) = (i + 1, j + 1)
			tij = t[i][j]
			min_dist = 1000
			for n_x in range(101):
				for n_y in range(101):
					dist = x * n_x + y * n_y + edge[n_x][n_y]
					if dist < min_dist:
						min_dist = dist
			if tij != min_dist:
				impossible()
	print('Possible')
	print(202, 101 * 101 + 200)
	for u in range(1, 101):
		print(u, u + 1, 'X')
	for u in range(102, 202):
		print(u, u + 1, 'Y')
	for n_x in range(101):
		for n_y in range(101):
			print(n_x + 1, 202 - n_y, edge[n_x][n_y])
	print(1, 202)
main()


def solve(x_max, y_max, d):
	c_table = [[-1] * 100 for _ in range(100)]
	for a in range(100):
		c_table_a = c_table[a]
		for x in range(x_max):
			ax = a * (x + 1)
			dx = d[x]
			for b in range(100):
				c = -1
				for y in range(y_max):
					c = max(c, dx[y] - ax - b * (y + 1))
				c_table_a[b] = max(c_table_a[b], c)
	ab_max = 0
	c_set = {}
	for x in range(x_max):
		dx = d[x]
		for y in range(y_max):
			dxy = d[x][y]
			f = False
			for a in range(100):
				c_table_a = c_table[a]
				ax = a * (x + 1)
				for b in range(100):
					if dxy == ax + b * (y + 1) + c_table_a[b]:
						ab_max = max(ab_max, a, b)
						c_set[a, b] = c_table_a[b]
						f = True
						break
				if f:
					break
			if not f:
				print('Impossible')
				return
	print('Possible')
	print('{} {}'.format((ab_max + 1) * 2, ab_max * 2 + len(c_set)))
	for i in range(ab_max):
		print('{} {} X'.format(i + 1, i + 2))
	for i in range(ab_max):
		print('{} {} Y'.format(ab_max + i + 3, ab_max + i + 2))
	for (k, c) in c_set.items():
		print('{} {} {}'.format(k[0] + 1, k[1] + ab_max + 2, c))
	print('{} {}'.format(1, ab_max + 2))

def main():
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	d = [list(map(int, input().split())) for _ in range(A)]
	solve(A, B, d)
main()


(a, b) = map(int, input().split())
distances = [list(map(int, input().split())) for _ in range(a)]
n = 202
m = 0
g = [[] for _ in range(n)]
for i in range(100):
	g[i].append((i + 1, 'X'))
	m += 1
for i in range(100):
	g[i + 101].append((i + 102, 'Y'))
	m += 1
for p in range(0, 101):
	for q in range(0, 101):
		r = -10000000
		for i in range(a):
			for j in range(b):
				r = max(r, distances[i][j] - p * (i + 1) - q * (j + 1))
		if r >= 0:
			g[p].append((n - q - 1, r))
			m += 1
for i in range(a):
	for j in range(b):
		d = [float('inf')] * n
		d[0] = 0
		s = [0]
		while s:
			p = s.pop()
			for (to, dist) in g[p]:
				if dist == 'X':
					dist = i + 1
				elif dist == 'Y':
					dist = j + 1
				s.append(to)
				d[to] = min(d[to], d[p] + dist)
		if d[-1] != distances[i][j]:
			print('Impossible')
			exit(0)
print('Possible')
print(n, m)
for i in range(n):
	for (node, dist) in g[i]:
		print(i + 1, node + 1, dist)
print(1, n)