ড্রোন রোভার (Drone Rovers)

CPU: 0.5s
Memory: 512MB


মঙ্গলে বসতি স্থাপনের জন্য উপযুক্ত স্থান নির্বাচনে প্রাথমিক অভিযান চলছে। এ কাজে ব্যবহার করা হচ্ছে দুটি ড্রোন রোভার। কেন্দ্রীয় স্টেশন থেকে তাদেরকে বিভিন্ন দিকে যাবার নির্দেশ দেওয়া হয়। এরা সেই অনুযায়ী বিভিন্ন স্থানে গিয়ে ভূতাত্ত্বিক জরিপ চালায়। প্রাথমিকভাবে উদ্দিষ্ট অঞ্চলকে ৮ বাই ৮ আকারের ছকে ভাগ করা হয়েছে। সর্ববামের এবং নিচের ঘরটির স্থানাংক (০,০) এবং সবথেকে উপরের ডানের ঘরটির স্থানাংক (৭,৭)

শুরুতে ড্রোন দুটো এই ছকের ভিন্ন ভিন্ন ঘরে অবস্থান করে। কেন্দ্রীয় স্টেশন থেকে কোনো ড্রোনকে বাম, ডান, উপর বা নিচে সরার জন্য নির্দেশ দেওয়া হতে পারে। নির্দেশ আসে ইংরেজী L, R, U বা D হরফ আকারে, যেগুলো যথাক্রমে বাম, ডান, উপর বা নিচের দিকে এক ঘর সরার নির্দেশ করে। দুটি ড্রোনকেই এভাবে একের পর এক বিভিন্ন দিকে যাবার নির্দেশ দেওয়া হয়। তারা যেহেতু একই ছকের মধ্যে চলাফেরা করছে, তাই লক্ষ্য রাখতে হয় যেন তারা একে অপরের সাথে সংঘর্ষ না করে।

ড্রোনগুলোর প্রাথমিক অবস্থান এবং তাদেরকে যেসব নির্দেশ দেওয়া হবে তার তালিকা তোমাকে বলা থাকবে। তোমার কাজ একটা প্রোগ্রাম লেখা যা আগে থেকে বলে দেবে, এইসব নির্দেশ মেনে চললে ড্রোন দুটোর সংঘর্ষ হবে কি না।

নির্দেশ তালিকাটি একটা স্ট্রিং আকারে দেওয়া থাকে (০ থেকে ইনডেক্স করা)। যার জোড় ইন্ডেক্সের (উল্লেখ্য ০ সংখ্যাটি জোড়) নির্দেশগুলি প্রথম ড্রোন, এবং বিজোড় ইন্ডেক্সের নির্দেশগুলি দ্বিতীয় ড্রোনটির জন্য। কেন্দ্রীয় স্টেশন এই স্ট্রিং এর শুরু থেকে একটা একটা করে হরফ পড়ে, এবং হরফের নির্দেশটি যে ড্রোনের জন্য প্রযোজ্য তার কাছে পাঠিয়ে দেয়। একটি ড্রোন সেই নির্দেশ মেনে সরার পর, পরবর্তি নির্দেশটি অন্য ড্রোনকে দেওয়া হয়। এভাবে ধাপে ধাপে দুইটি ড্রোনকেই চালনা করা হয়।

যেমন- “LLRU” এই নির্দেশ স্ট্রিং এর ক্ষেত্রে- প্রথমে প্রথম ড্রোনটি নিজের স্থান থেকে একঘর বামে সরবে, এর পর দ্বিতীয় ড্রোনটি নিজের স্থান থেকে এক ঘর বামে সরবে, এরপর প্রথমটি একঘর ডানে সরবে, এবং সব শেষে দ্বিতীয়টি একঘর উপরে সরবে। ৮ বাই ৮ ছকের বাম ডান উপর বা নিচের দিককার সীমানা সংলগ্ন কোনো ঘরে অবস্থানকালে যদি কোনো ড্রোনকে সীমানা অতিক্রমের নির্দেশ দেওয়া হয় তাহলে সেই ধাপে ড্রোনটি নির্দেশটি অমান্য করে যে ঘরে ছিলো সে ঘরেই থাকবে। লক্ষ্যণীয়, একটি ড্রোন যদি শুরুতে (x,y) অবস্থানে থাকে তাহলে তার বাম, ডান, উপরের এবং নিচের পজিশনগুলো হবে যথাক্রমে (x-1,y), (x+1,y), (x,y+1), (x,y-1)।

A pioneer mission is operating to select the place for establishing a colony on the planet Mars. For this two drone rovers are being used. The central station commands them to move towards various directions and they move accordingly to perform geological survey. Initially the intended area is divided into an 8 by 8 grid. Lower left square of the grid has co-ordinate (0,0) and upper-right square has co-ordinate (7,7).

The two drones initially stays on different squares of the grid. The central station can command any drone to move left, right, up or down. These commands are sent as english letters L, R, U or D, which represents an instruction for moving one square towards left, right, up, or down respectively. Both of the drones receive commands one by one to move towards various direction. As they are moving in the same grid, extra care must be taken so that they do not collide with each other.

You are given the initial position of the drones along with the command list. Your task is to write a program which can detect if a collision is going to happen or not.

The command list is given as a string indexed from 0. The letters in the even index (note that, the number 0 is even) of the string indicate the commands for first drone, and the odd index indicate the commands for the second drone. The central station will read this string from the beginning to the end one letter at a time and send each of the commands to the respective drone. Once a drone moves according to a command, the next command is given to the other drone. This way both of the drones are moved step by step.

For example, if “LLRU” is the command string then the first drone will move one square to the left, after that the second drone will move one square to the left, then the first drone will move one square to the right and finally the second drone will move one square to the up direction. While staying in a square adjacent to the boundary of the 8 by 8 grid, if a drone is given a command that instructs it to cross the boundary then the drone will ignore the command and remain where it is. Note that, if a drone is initially at position (x,y), the positions in its left, right, up and down are (x-1,y), (x+1,y), (x,y+1), (x,y-1).


ইনপুটের বর্ণনা

প্রথম লাইনে একটি ইন্টিজার সংখ্যা T দেওয়া থাকবে, যা টেস্ট কেস সংখ্যা নির্দেশ করছে। এর পর T সংখ্যক লাইন থাকবে যার প্রতিটিতে স্পেস দিয়ে আলাদা করা চারটি ইন্টিজার x1, y1, x2, y2 এবং একটি স্ট্রিং S দেওয়া থাকবে। যেখানে ছকের সবচেয়ে নিচের বামের ঘরটিকে মূলবিন্দু (0,0) ধরে, (x1,y1) প্রথম ড্রোনটির শুরুর অবস্থান এবং (x2,y2) দ্বিতীয় ড্রোনটির শুরুর অবস্থান প্রকাশ করে। এবং স্ট্রিং S টি নির্দেশ তালিকা প্রকাশক করে। S অনুযায়ী কেন্দ্রীয় স্টেশন ড্রোন দুটোকে পরিচালনা করে। ২টি ড্রোনের প্রাথমিক অবস্থান ভিন্ন হবে।

1<= T <= 1000

0<=x1, y1, x2, y2<=7

স্ট্রিং S এর দৈর্ঘ্য 100 বা তার কম।


Input Specification

In the first line there will be an integer T denoting the number of test cases. The next T lines each will contain four integers x1, y1, x2, y2 and a string S separated by space. Here (x1,y1) is the initial location of the first drone and (x2,y2) is the initial location of the second drone. These location are given by considering the lower left square if the grid as the origin (0,0). And the string S represents the command list. The central station drives the two drones according to S. Initially two drones will be in separate squares.

1<= T <= 1000

0<=x1, y1, x2, y2<=7

The length of string S is less than or equal to 100.


আউটপুটের বর্ণনা

প্রতি টেস্ট কেসের জন্য আলাদা লাইন ছাপাতে হবে। সেই টেস্ট কেসে যদি সংঘর্ষ অনিবার্য হয় তাহলে লাইনটিতে COLLISION আর না হলে SAFE ছাপাতে হবে। কেস নাম্বার প্রিন্ট করতে অবশ্যই ভুলো না, স্যাম্পল ইনপুট/আউটপুট দেখ।


Output Specification

For each test case print the case a separate line, where if a collision is imminent then print COLLISION otherwise print SAFE. Don’t forget to print the case numbers too. See sample I/O for exact formatting.


Sample

InputOutput
3 0 0 3 0 RLRL 7 7 6 7 RRU 0 0 5 5 LRLRLCase 1: COLLISION Case 2: COLLISION Case 3: SAFE