import java.util.*;

public class RobotRouting {

	static final long startTime = System.currentTimeMillis();
	static final Random rand = new Random(12345);
	static final int INF = 100000000;
	static final int MAXT = 50000;
	static final int TIMESLOT = 500;

	static final int timeSinceStart() {
		return (int)(System.currentTimeMillis()-startTime)/100;
	}

	String[] route(int C, int M, int N, int K, int rowGap, int colGap, int[] robotX, int[] robotY, String[] prods, int[] taskID, int[] taskY) {
		boolean lanes = C <= 5;
		String[] ans = null;
		int bestVal = 1000000002;
		int rounds = 0;
		while (true) {
			++rounds;
			RealDeal rd = new RealDeal();
			rd.lanes = lanes;
			lanes = !lanes;
			String[] alt = rd.route(C, M, N, K, rowGap, colGap, robotX, robotY, prods, taskID, taskY);
			int score;
			if (rd.completedTasks == 0) {
				score = 1000000001;
			} else if (rd.completedTasks == 10000) {
				score = alt.length;
			} else {
				score = 1000000000/rd.completedTasks;
			}
			if (score < bestVal) {
				bestVal = score;
				ans = alt;
			}
			int time = timeSinceStart();
			int timeEstimate = ((rounds+1)*time)/rounds;
			if (timeEstimate+40 >= TIMESLOT) break;
		}
		return ans;
	}

	static class Position {
		final int x, y;
		Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override public String toString() {
			return "("+x+","+y+")";
		}
	}

	static enum Dir {
		R(1, 0),
		U(0, -1),
		D(0, 1),
		L(-1, 0);
		final int dx, dy;
		final String action;
		Dir opposite;
		Dir(int dx, int dy) {
			this.dx = dx;
			this.dy = dy;
			action = toString();
		}
	}
	static {
		Dir.U.opposite = Dir.D;
		Dir.D.opposite = Dir.U;
		Dir.L.opposite = Dir.R;
		Dir.R.opposite = Dir.L;
	}
	static final Dir[] dirs = {Dir.R, Dir.U, Dir.D, Dir.L};

	static enum MoveState {
		STAY,
		LOADING,
		WANT_TO_GO,
		PROCESSING,
		MOVED;
	}

	static enum Phase {
		OUT,
		DELIVERY,
		DONOTHING;
	}

	static class Option implements Comparable<Option> {
		RealDeal.Location loc;
		Dir dir;
		boolean legal;
		int improvement;
		public int compareTo(Option o) {
			int d = o.improvement - improvement;
			if (d != 0) return d;
			if (legal == o.legal) return 0;
			if (legal) return -1;
			return 1;
		}
		public String toString() {
			return "Option " + improvement + " " +legal+" "+ dir+" "+loc;
		}
	}


private class RealDeal {

	/*** VARIABLES ***/

	boolean lanes;
	int minCritic;
	boolean dense;
	String[][] actions = new String[MAXT+10][];

	int X, Y, R, P;
	int T;
	int C, M, N, K;
	int RG, CG;

	int completedTasks;
	int numAssignments;

	Location[][] map;
	Location[] allLocs;
	Robot[] robots;
	Product[] products;
	Collection<Location> corners = new ArrayList<Location>();
	LinkedList<Task>[] dropoffs;
	LinkedList<Assignment>[] queue;
	LinkedList<Assignment> assignments = new LinkedList<Assignment>();
	SortedSet<Robot> critical = new TreeSet<Robot>();

	Dir[] colForbidden, rowForbidden;
	boolean[] colShelf, rowShelf;

	int[][] cornerDist;


	/*** CLASSES ***/

	class Assignment implements Comparable<Assignment> {
		final List<Task> tasks = new ArrayList<Task>();
		final int y;
		final int sortOrder;
		final Location destination;
		int ind;
		int startLength;
		int numTasks;
		Assignment(int y, int order) {
			this.y = y;
			this.sortOrder = order;
			destination = map[0][y];
		}
		void addTask(Task t) {
			++numTasks;
			tasks.add(t);
		}
		int startY() {
			return tasks.get(0).closestLocation.y;
		}
		Task get() {
			if (ind < numTasks) {
				return tasks.get(ind++);
			} else return null;
		}
		public int compareTo(Assignment a) {
			return sortOrder - a.sortOrder;
		}
		int remaining(Location loc) {
			return remaining(loc, ind-1, numTasks);
		}
		int remaining(Location loc, int ind, int M) {
			if (ind >= M) {
				return wdist(loc, destination);
			} else {
				Task chosen = tasks.get(ind);
				int ans = wdist(loc, chosen.closestLocation);
				for (int i=ind; i+1<M; ++i) {
					ans += tasks.get(i).distToNext;
				}
				ans += wdist(tasks.get(M-1).closestLocation, destination);
				return ans;
			}
		}
		int fullLength() {
			if (tasks.isEmpty()) return -1;
			return remaining(tasks.get(0).closestLocation, 0, numTasks);
		}
	}

	class Task implements Comparable<Task> {
		final Location destination;
		final Product p;
		Location closestLocation;
		final int y;
		final int sortOrder, realDist;
		int distToNext;
		boolean taken;
		Task(Product p, int y) {
			this.p = p;
			this.y = y;
			destination = map[0][y];
			int bestVal = INF;
			int bestDist = -1;
			Location best = null;
			for (Location loc : p.locs) {
				int dist = wdist(loc, destination);
				int val = dense ? Math.abs(loc.y - y) : dist;
				if (val < bestVal) {
					bestVal = val;
					best = loc;
					bestDist = dist;
				}
			}
			closestLocation = best;
			sortOrder = bestVal;
			realDist = bestDist;
		}
		public int compareTo(Task b) {
			return sortOrder - b.sortOrder;
		}
		@Override public String toString() {
			return String.format("Task %d %s", p.id, closestLocation);
		}
	}

	class Product {
		final int id;
		final Location[] locs;
		Product(int id, String spec) {
			this.id = id;
			String[] ss = spec.split(" ");
			int n = ss.length;
			List<Location> ls = new ArrayList<Location>();
			for (int i=0; i<n; ++i) {
				String[] ps = ss[i].split(",");
				int x = Integer.parseInt(ps[0]);
				int y = Integer.parseInt(ps[1]);
				for (Dir d : dirs) {
					Location l = add(new Position(x, y), d);
					if (l != null) ls.add(l);
				}
			}
			locs = ls.toArray(new Location[0]);
		}
	}

	class Edge {
		final Location nabo;
		final int dist;
		Edge(Location nabo, int dist) {
			this.nabo = nabo;
			this.dist = dist;
		}
	}

	int LID;
	class Location extends Position {
		final int id = LID++;
		Location(int x, int y) {
			super(x, y);
			if (!rowShelf[y] && !colShelf[x]) {
				corner = corners.size();
				corners.add(this);
			} else corner = -1;
		}
		int primaryTargets;
		Robot robot;
		final int corner;
		boolean isCorner() { return corner >= 0; }
		Collection<Edge> edges;
		int myDist;
		boolean isExtremeCorner() {
			return (x==X-1 || x==0) && (y==Y-1 || y==0);
		}
	}

	int RID;
	class Robot implements Comparable<Robot> {
		final int sx, sy;
		final int id;
		Robot(int x, int y) {
			sx = x;
			sy = y;
			id = RID++;
			location = map[x][y];
			location.robot = this;
		}
		int remainingOfAssignment;
		Location location;
		Option[] options = new Option[4];
		int opts;
		Location goal;
		Task activeTask;
		int deadline;
		int depth;

		List<Robot> waiting = new ArrayList<Robot>();
		Assignment assignment;
		MoveState moveState;
		Phase phase = Phase.OUT;
		boolean removed = true;
		void updateCritical() {
			if (!removed) {
				critical.remove(this);
				removed = true;
			}
			if (assignment == null) return;
			switch (phase) {
			case DONOTHING: return;
			case OUT:
				remainingOfAssignment = assignment.remaining(location);
				break;
			case DELIVERY:
				remainingOfAssignment = wdist(location, assignment.destination);
			}
			if (remainingOfAssignment >= minCritic) {
				critical.add(this);
				removed = false;
			}
		}
		void addAction(String action) {
			actions[T][id] = action;
		}
		public int compareTo(Robot r) {
			int d = r.remainingOfAssignment - remainingOfAssignment;
			if (d == 0) d = r.id - id;
			return d;
		}
		void move(Location to) {
			moveState = MoveState.MOVED;
			addAction(subtract(to, location).action);
			if (location.robot == this) location.robot = null;
			to.robot = this;
			opts = 0;
			location = to;
			updateCritical();
		}
		Location getGoal() {
			switch (phase) {
			case OUT:
				if (assignment == null) {
					assignment = takeAssignment(this);
					if (assignment == null) {
						phase = Phase.DONOTHING;
						deadline = -1;
						return null;
					}
				}
				activeTask = assignment.get();
				if (activeTask == null) {
					phase = Phase.DELIVERY;
					return getGoal();
				}
				updateCritical();
				return activeTask.closestLocation;
			case DELIVERY:
				return assignment.destination;
			default:
				return null;
			}
		}
		String onsite() {
			switch (phase) {
			case OUT:
				String action = "T"+activeTask.p.id;
				activeTask = null;
				return action;
			case DELIVERY:
				if (assignment.tasks.isEmpty()) {
					phase = Phase.OUT;
					activeTask = null;
					assignment = null;
					return null;
				}
				Task t = assignment.tasks.get(assignment.numTasks-1);
				++completedTasks;
				assignment.tasks.remove(t);
				--assignment.numTasks;
				return "P"+t.p.id;
			default:
				return null;
			}
		}
		void expressIntentions() {
			if (phase == Phase.DONOTHING) {
				if (T == deadline) {
					phase = Phase.DELIVERY;
					deadline = -1;
					expressIntentions();
					return;
				}
				opts = 0;
				for (int i=0; i<4; ++i) {
					Option o = new Option();
					o.dir = dirs[i];
					o.loc = add(location, o.dir);
					if (o.loc == null || (o.loc.x == 0 && !lanes)) {
						continue;
					} else {
						int score = 1 + rand.nextInt(4);
						if (o.loc.x < 4) { //  || o.loc.x*3 < X
							if (o.dir == Dir.R) score += 50;
							else if (o.dir != Dir.L) score += 20;
						}
						o.improvement = score;
						options[opts++] = o;
					}
				}
				moveState = MoveState.WANT_TO_GO;
				treat();
			} else {
				if (goal == null) {
					goal = getGoal();
					if (goal == null) {
						expressIntentions();
						return;
					}
				}
				if (location == goal) {
					String action = onsite();
					goal = null;
					if (action == null) {
						expressIntentions();
						return;
					} else {
						moveState = MoveState.LOADING;
						addAction(action);
					}
				} else {
					boolean problem = !lanes && location.x == 1 && location.y == goal.y && goal.x == 0 && goal.robot != null;
					if (problem) {
						phase = Phase.DONOTHING;
						deadline = T + 25;
						goal = null;
						expressIntentions();
						return;
					}
					opts = 0;
					int currentDist = wdist(location, goal);
					boolean issue = !lanes && currentDist == 2 && goal.robot != null && phase == Phase.DELIVERY;
					boolean sidestep = lanes && currentDist == 2 && phase == Phase.DELIVERY;
					for (int i=0; i<4; ++i) {
						Dir dir = dirs[i];
						Location l = add(location, dir);
						if (l == null) {
							continue;
						} else {
							Option o = new Option();
							o.dir = dir;
							o.loc = l;
							o.improvement = currentDist - wdist(l, goal);
							if (sidestep && dir == Dir.L) {
								++o.improvement;
							}
							if (issue) {
								if (o.improvement == 1) {
									o.improvement = -15;
								}
								if (o.loc.x == 0 && o.loc.robot == null) o.improvement = 1;
							}
							options[opts++] = o;
						}
					}
					treat();
					moveState = MoveState.WANT_TO_GO;
				}
			}
		}
		private void treat() {
			for (int i=0; i<opts; ++i) {
				Option o = options[i];
				o.legal = allowed(location, o.dir);
			}
			Arrays.sort(options, 0, opts);
			for (int i=0; i<opts; ++i) {
				Option o = options[i];
				if (!o.legal) continue;
				o.loc.primaryTargets++;
				break;
			}
		}
		@Override public String toString() {
			return "R "+id+" "+phase+" "+location+" "+remainingOfAssignment+" "+moveState;
		}
	}

	/*** LOGIC ***/

	boolean clear(Location l, int depth, Robot from) {
		if (l.robot == null) {
			return true;
		} else {
			move(l.robot, depth+1, from);
			return l.robot == null;
		}
	}

	void move(Robot r, int depth, Robot from) {
		if (r == null) return;
		if (from != null) r.waiting.add(from);
		switch (r.moveState) {
		case PROCESSING:
			if (r.depth+2 < depth)
				r.location.robot = null;
			return;
		case WANT_TO_GO:
			r.moveState = MoveState.PROCESSING;
			r.depth = depth;
			boolean first = true;
			for (int i=0; i<r.opts; ++i) {
				Option o = r.options[i];
				boolean ignore = !lanes && !first && o.loc.x==0;
				first = false;
				if (ignore) continue;
				if (!o.legal && o.loc.primaryTargets > 0) continue;
				if (o.improvement <= 0 && depth <= 10 && !(depth > 3 && r.location.isCorner() && !o.loc.isExtremeCorner())) {
					continue;
				}
				if (clear(o.loc, depth, r)) {
					for (Option o2 : r.options) {
						if (!o2.legal) continue;
						if (o2 != o) o2.loc.primaryTargets--;
						break;
					}
					r.move(o.loc);
					return;
				}
			}
			for (Option o2 : r.options) {
				if (!o2.legal) continue;
				o2.loc.primaryTargets--;
				break;
			}
			r.moveState = MoveState.STAY;
			return;
		default:
			return;
		}
	}

	Assignment helpOut(Robot cool) {
		Robot bestR = null;
		int bestV = 0;
		int bestInd = -1;
		int looped = 0;
		int checked = 0;
		for (Robot r : critical) {
			if (r == cool) continue;
			++looped;
			if (looped > 300) break;
			if (checked > 10) break;
			if (r.phase != Phase.OUT) continue;
			Assignment a = r.assignment;
			int bef = a.remaining(r.location);
			++checked;
			for (int ind = a.ind; ind < a.numTasks; ++ind) {
				int ham = a.remaining(r.location, a.ind-1, ind);
				int meg = a.remaining(cool.location, ind, a.numTasks);
				int val = bef - Math.max(ham, meg);
				if (val > bestV) {
					bestV = val;
					bestInd = ind;
					bestR = r;
				}
			}
		}
		if (bestR == null) return null;
		Assignment old = bestR.assignment;
		Assignment ny = new Assignment(old.y, -99);
		for (int i=bestInd; i<old.numTasks; ++i) {
			ny.addTask(old.tasks.get(i));
		}
		old.tasks.removeAll(ny.tasks);
		old.numTasks -= ny.numTasks;
		bestR.updateCritical();
		return ny;
	}

	void defineTraffic() {
		colForbidden = new Dir[X];
		Dir[] forbidden = {Dir.U, Dir.D};
		int ind = 0;
		for (int i=0; i<X; ++i) {
			if (i+2==X) ind = 1;
			if (!colShelf[i]) {
				colForbidden[i] = forbidden[ind];
				ind = 1-ind;
			}
		}
		colForbidden[0] = Dir.D;
		forbidden = new Dir[]{Dir.L, Dir.R};
		rowForbidden = new Dir[Y];
		ind = 0;
		for (int i=0; i<Y; ++i) {
			if (i+2==Y) ind = 0;
			if (!rowShelf[i]) {
				rowForbidden[i] = forbidden[ind];
				ind = 1-ind;
			}
		}
	}

	boolean allowed(Location a, Dir dir) {
		if (a.x == 0) return dir == Dir.R || (lanes && dir == Dir.U);
		if (a.x == 1 && dir==Dir.L) return true;
		Dir f = colForbidden[a.x];
		if (f != null && f.opposite == dir) return true;
		f = rowForbidden[a.y];
		if (f != null && f.opposite == dir) return true;
		return false;
	}

	void calcDistances() {
		int n = corners.size();
		cornerDist = new int[n][n];
		for (int[] a : cornerDist) {
			Arrays.fill(a, INF);
		}
		for (int i=0; i<n; ++i) cornerDist[i][i] = 0;
		for (Location corner : corners) {
			corner.edges = new ArrayList<Edge>();
			for (Dir dir : dirs) {
				if (!allowed(corner, dir)) continue;
				int dist = 0;
				Location loc = corner;
				while (true) {
					loc = add(loc, dir);
					++dist;
					if (loc == null) break;
					if (loc.isCorner()) {
						corner.edges.add(new Edge(loc, dist));
						break;
					}
				}
			}
		}
		for (Location corner : corners) {
			for (Location l : corners) l.myDist = INF;
			corner.myDist = 0;
			TreeSet<Location> q = new TreeSet<Location>(new Comparator<Location>() {
				public int compare(Location a, Location b) {
					int d = a.myDist - b.myDist;
					if (d != 0) return d;
					return a.id - b.id;
				}
			});
			q.add(corner);
			while (!q.isEmpty()) {
				Location loc = q.first();
				q.remove(loc);
				cornerDist[corner.corner][loc.corner] = loc.myDist;
				for (Edge e : loc.edges) {
					int alt = loc.myDist + e.dist;
					if (alt < e.nabo.myDist) {
						q.remove(e.nabo);
						e.nabo.myDist = alt;
						q.add(e.nabo);
					}
				}
			}
		}
	}

	void makeAssignments(int y) {
		LinkedList<Task> tasks = dropoffs[y];
		Collections.sort(tasks);
		int n = tasks.size();
		int k = (n-1)/C+1;
		int med = n/k;
		Assignment[] A = new Assignment[k];
		int cnt = 0;
		for (int i=0; i<k; ++i) {
			Task head = tasks.removeFirst();
			Assignment a = A[i] = new Assignment(y, k-i-1);
			assignments.add(a);
			++numAssignments;
			head.distToNext = head.realDist;
			a.addTask(head);
			int s = med;
			if ((i+1)*(med+1)+(k-i-1)*med<=n) ++s;
			for (int j=1; j<s; ++j) {
				int bv = INF;
				Task bt = null;
				Task last = a.tasks.get(a.numTasks-1);
				for (Task t : tasks) {
					for (Location loc : t.p.locs) {
						int v = manhattan(last.closestLocation, loc);
						if (v >= bv) continue;
						++cnt;
						v = wdist(loc, last.closestLocation);
						if (v < bv) {
							bv = v;
							bt = t;
							t.closestLocation = loc;
						}
					}
				}
				bt.distToNext = bv;
				a.addTask(bt);
				tasks.remove(bt);
			}
			Collections.reverse(a.tasks);
		}
	}

	void makeMoves() {
		List<Robot> shuffled = Arrays.asList(robots);
		Collections.shuffle(shuffled, rand);
		shuffled.toArray(robots);
		Set<Robot> moved = new HashSet<Robot>();
		for (Robot r1 : robots) {
        	if (r1.moveState == MoveState.WANT_TO_GO && r1.location.x==0 && moved.add(r1)) {
        		move(r1, 0, null);
        	}
        }
		Robot[] arr = new Robot[10];
		int cnt = 0;
		for (Iterator<Robot> it = critical.iterator(); it.hasNext() && cnt<arr.length; ++cnt) {
			arr[cnt] = it.next();
        }
		for (Robot r : arr) {
        	if (r!=null && r.moveState == MoveState.WANT_TO_GO && moved.add(r)) {
        		move(r, 0, null);
        	}
		}
		for (Robot r1 : robots) {
        	if (r1.moveState == MoveState.WANT_TO_GO && r1.phase == Phase.OUT && moved.add(r1)) {
        		move(r1, 0, null);
        	}
        }
		for (Robot r1 : robots) {
        	if (r1.moveState == MoveState.WANT_TO_GO && r1.phase != Phase.DONOTHING && moved.add(r1)) {
        		move(r1, 0, null);
        	}
        }
		for (Robot r1 : robots) {
        	if (r1.moveState == MoveState.WANT_TO_GO && !moved.contains(r1))
        		move(r1, 0, null);
        }
	}

	void execute() {
		while (completedTasks < 10000 && T < MAXT) {
			actions[T] = new String[R];

			minCritic -= 5;
			int len = 100;
			if (critical.size() > len) {
				Iterator<Robot> it = critical.iterator();
				for (int i=0; i<len; ++i) {
					minCritic = it.next().remainingOfAssignment;
				}
			}
			for (Location l : allLocs) l.primaryTargets = 0;
			for (Robot r : robots) {
				r.waiting.clear();
            	r.expressIntentions();
            }
			makeMoves();
			moveAlong();
			for (Location l : allLocs) l.primaryTargets = 0;
			for (Robot r : robots) {
				if (r.moveState == MoveState.STAY) {
					r.moveState = MoveState.WANT_TO_GO;
				}
			}
			makeMoves();
			for (Robot r : robots) {
				r.opts = 0;
				if (r.moveState == MoveState.STAY) {
					r.addAction("S");
				}
				r.moveState = null;
			}
			++T;

			int tid = timeSinceStart();
			if (tid > TIMESLOT) break;

		}
	}

	String[] generateReturn() {
		String[] ans = new String[T];
		for (int t=0; t<T; ++t) {
			StringBuilder sb = new StringBuilder();
			for (int r = 0; r<R; ++r) {
				sb.append(actions[t][r]);
			}
			ans[t] = sb.toString();
		}
		return ans;
	}

	void moveAlong() {
		for (Robot r : robots) {
			if (r.location.isCorner() && r.moveState == MoveState.STAY) {
				boolean wait = false;
				for (Robot f : r.waiting) {
					if (f.moveState == MoveState.STAY) wait = true;
				}
				if (!wait) continue;
				for (Dir d : dirs) {
					Location loc = add(r.location, d);
					if (loc != null && loc.robot == null && (loc.x>0 || lanes) && !loc.isExtremeCorner()) {
						r.move(loc);
						break;
					}
				}
			}
		}
	}

	boolean lastTaken;
	Assignment takeAssignment(Robot r) {
		if (lastTaken) return helpOut(r);
		int biggest = 0;
		for (int y=0; y<Y; ++y) {
			int x = queue[y].size();
			if (x > biggest) biggest = x;
		}
		if (biggest == 0) {
			lastTaken = true;
			return helpOut(r);
		}
		if (r.location.x == 0) {
			int val = INF;
			int bestY = -1;
			for (int y=0; y<Y; ++y) {
				int x = queue[y].size();
				if (x==0) continue;
				int score = 10*(biggest-x) + Math.abs(y-r.location.y);
				if (score < val) {
					val = score;
					bestY = y;
				}
			}
			return queue[bestY].removeFirst();
		} else {
			int val = INF;
			int bestY = -1;
			Assignment ans = null;
			for (int dy = 0; dy<Y && dy<val; ++dy) {
				for (int sign=-1; sign<=1; sign+=2) {
					int y = r.location.y+dy*sign;
					if (y<0 || y>=Y) continue;
					for (Assignment a : queue[y]) {
						int d = wdist(r.location, a.tasks.get(0).closestLocation);
						if (d < val) {
							val = d;
							ans = a;
							bestY = y;
						}
					}
				}
			}
			queue[bestY].remove(ans);
			return ans;
		}
	}

	void initialDist() {
		int sum = 0;
		for (Assignment a : assignments) {
			sum += a.startLength = a.fullLength();
		}
		int ant = assignments.size();
		int av = sum / ant;
		int H = (3 * av)/2;
		if (ant < R) H = -1;
		int M = R/2;
		Collections.sort(assignments,
			new Comparator<Assignment>() {
				public int compare(Assignment a, Assignment b) {
					return b.startLength - a.startLength;
				}
		});
		int did = 0;
		boolean stop = false;
		for (Assignment a : assignments) {
			if (a.startLength < H) stop = true;
			if (H!=-1 && did>=M) stop = true;
			if (!stop) {
				++did;
				Location startLoc = a.tasks.get(0).closestLocation;
				int bestV = INF;
				Robot bestR = null;
				for (Robot r : robots) {
					if (r.assignment != null) continue;
					int val = manhattan(r.location, startLoc);
					if (val >= bestV) continue;
					val = wdist(r.location, startLoc);
					if (val >= bestV) continue;
					bestV = val;
					bestR = r;
				}
				if (bestR == null) {
					stop = true;
				} else {
					bestR.assignment = a;
				}
			}
			if (stop) {
				queue[a.startY()].add(a);
			}
		}
	}

	/*** UTILITY METHODS ***/

	int manhattan(Position a, Position b) {
		return Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
	}

	int wdist(Location a, Location b) {
		if (a == b) return 0;

		if (lanes && b.x==0 && a.x==1) {
			int h = a.y - b.y;
			if (h>=0) return h+1;
		}

		if (b.x == 0 && !lanes) {
			return 1+wdist(a, add(b, Dir.R));
		}
		if (a.x == 0 && !lanes) {
			return 1+wdist(add(a, Dir.R), b);
		}

		int target1;
		int end1 = 0;
		if (b.isCorner()) {
			target1 = b.corner;
		} else {
			if (!rowShelf[b.y]) {
				int dx = rowForbidden[b.y].dx;
				int x = b.x;
				while (colShelf[x]) {
					x += dx;
					++end1;
				}
				target1 = map[x][b.y].corner;
			} else {
				int dy = colForbidden[b.x].dy;
				int y = b.y;
				while (rowShelf[y]) {
					y += dy;
					++end1;
				}
				target1 = map[b.x][y].corner;
			}
		}
		if (a.isCorner()) {
			return cornerDist[a.corner][target1] + end1;
		} else {
			int val = 0;
			Location loc;
			if (!rowShelf[a.y]) {
				int dx = rowForbidden[a.y].opposite.dx;
				int x = a.x;
				while (colShelf[x]) {
					x += dx;
					++val;
					if (x==b.x && a.y==b.y) return val;
				}
				loc = map[x][a.y];
			} else {
				int dy = colForbidden[a.x].opposite.dy;
				int y = a.y;
				while (rowShelf[y]) {
					y += dy;
					++val;
					if (a.x==b.x && y==b.y) return val;
				}
				loc = map[a.x][y];
			}
			return val + cornerDist[loc.corner][target1] + end1;
		}
	}

	boolean hasShelf(int pos, int size, int spacing, int num) {
		pos -= 2;
		if (pos<0) return false;
		int a = pos / (size + spacing);
		if (a >= num) return false;
		int mod = pos - a * (size + spacing);
		return mod < size;
	}

	Location add(Position p, Dir d) {
		int x = p.x+d.dx;
		int y = p.y+d.dy;
		if (x < 0 || x>=X || y<0 || y>=Y) return null;
		return map[x][y];
	}
	Dir subtract(Position to, Position from) {
		int dx = to.x - from.x;
		int dy = to.y - from.y;
		for (Dir dir : dirs) {
			if (dir.dx == dx && dir.dy == dy) return dir;
		}
		throw new RuntimeException("dir not found for "+to+" from "+from);
	}

	/*** MAIN METHOD ***/

	void initGeometry(int M, int N, int K, int rowGap, int colGap) {
		this.M = M;
		this.N = N;
		this.K = K;
		this.RG = rowGap;
		this.CG = colGap;
		X = 4 + K*M + (M-1)*colGap;
		Y = 4 + 2*N + (N-1)*rowGap;
		double density = ((double)R)/(X*Y);
		dense = density > 0.082;
		colShelf = new boolean[X];
		rowShelf = new boolean[Y];
		for (int i=0; i<X; ++i) colShelf[i] = hasShelf(i, K, CG, M);
		for (int i=0; i<Y; ++i) rowShelf[i] = hasShelf(i, 2, RG, N);
		map = new Location[X][Y];
		Collection<Location> allLs = new ArrayList<Location>();
		for (int x=0; x<X; ++x) {
			for (int y=0; y<Y; ++y) {
				if (!(colShelf[x] && rowShelf[y])) {
					allLs.add(map[x][y] = new Location(x, y));
				}
			}
		}
		allLocs = allLs.toArray(new Location[0]);
		defineTraffic();
		calcDistances();
	}

	@SuppressWarnings("unchecked")
	String[] route(int C, int M, int N, int K, int rowGap, int colGap, int[] robotX, int[] robotY, String[] prods, int[] taskID, int[] taskY) {
		this.C = C;
		R = robotX.length;
		initGeometry(M, N, K, rowGap, colGap);
		P = prods.length;
		robots = new Robot[R];
		products = new Product[P];
		Task[] tasks = new Task[10000];
		queue = new LinkedList[Y];
		dropoffs = new LinkedList[Y];
		for (int i=0; i<Y; ++i) {
			queue[i] = new LinkedList<Assignment>();
			dropoffs[i] = new LinkedList<Task>();
		}
		for (int i=0; i<R; ++i) {
			robots[i] = new Robot(robotX[i], robotY[i]);
		}
		for (int i=0; i<P; ++i) {
			products[i] = new Product(i, prods[i]);
		}
		for (int i=0; i<10000; ++i) {
			tasks[i] = new Task(products[taskID[i]], taskY[i]);
			dropoffs[taskY[i]].add(tasks[i]);
		}
		for (List<Task> list : dropoffs) {
			Collections.shuffle(list, rand);
		}
		for (int y=0; y<Y; ++y) {
        	makeAssignments(y);
        }
		initialDist();
		for (List<Assignment> list : queue) {
			Collections.shuffle(list, rand);
		}
		try {
			execute();
		} catch (Throwable t) {
			--T;
		}
		return generateReturn();
	}

}

}