মনে করো, তুমি "হ য ব র ল" নামের একটি শহরের মেয়র। যেমন আজব শহরটির নাম ঠিক তেমনই আজব শহরটির আকার। যদিও শহরের মানুষ অনেক ভালো। চলো প্রথমেই শহরের মানচিত্রটি দেখে নিই। কার্তেসিয়ান স্থানাঙ্ক অনুযায়ী শহরের টাউন হলটি শহরের একদম কেন্দ্রে অবস্থিত আর অন্যান্য স্থাপনাসমূহ এই টাউনহলের চারপাশেই অবস্থিত। খুব সহজভাবে বলতে আমরা শহরটির সীমানাটিকে একটি বৃত্তের মত চিন্তা করতে পারি।

অন্যান্য শহরগুলোর মত তোমার শহরও কোভিড-১৯ দ্বারা আক্রান্ত হয়েছে যার দরুন তোমাকে তোমার শহরের সকল শিক্ষা প্রতিষ্ঠান বন্ধ করতে হয়েছে। কিন্তু মেয়র হিসাবে তুমি চাও না তোমার শহরের শিক্ষার্থীরা পিছিয়ে পড়ুক। তাই তুমি সব শিক্ষার্থীর জন্য অনলাইন ক্লাস শুরু করতে চাও। কিন্তু তোমার এই উদ্যোগের একটি বড় অন্তরায় হচ্ছে শহরের সবার বাড়িতে ইন্টারনেট কানেকশন নেই। তাই, সকলের সুবিধার জন্য তুমি সবাইকে ব্রডব্যান্ড ইন্টারনেট কানেকশন দিতে চাও।

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

দুঃখজনকভাবে তোমার শহরের নেটওয়ার্ক ডিপার্টেমেন্টের কাছে K টি রিপিটার আছে এবং লকডাউনের কারনে তুমি অন্য কোথাও থেকে নতু্ন রিপিটার আনতে পারছো না।

তোমাকে তোমার শহরের টাউন হলের স্থানাঙ্ক (Xt,Yt) এবং প্রথম রিপিটারের স্থানাঙ্ক (X,Y) এবং শহরে থাকা রিপিটারের সংখ্যা দেওয়া আছে। ***তোমাকে বাকি রিপিটারগুলোর স্থানাঙ্ক বের করতে হবে যাতে করে প্রতিটি রিপিটারের জন্য তার পাশের রিপিটারের সাথে দুরত্ব সর্বোচ্চ হয়। ***

এই সমস্যাটির জন্য পাই এর মান acos(-1.0)

Input

ইনপুটের প্রথম লাইনে শুধুমাত্র একটি পূর্ণসংখ্যা T থাকবে যা টেস্টকেসের সংখ্যা নির্দেশ করে।
পরব্তী T লাইনে পাচটি সংখ্যা একটি লাইনে থাকবে। যথাক্রমেঃ Xt, Yt, X, Y , k যেখানে (Xt,Yt) টাউন হলের স্থানাংক এবং (X,Y) প্রথম রিপিটারের স্থানাংক নির্দেশ কওরে।

Constraints

1 ≤ T ≤ 25

প্রতিটি টেস্টকেসের জন্য নিশ্চিতভাবে বলা যায় যে Xt (-500 ≤ Xt ≤ 500), Yt (-500 ≤ Yt ≤ 500), X ( -500 ≤ X ≤ 500) , Y (-500 ≤ Y ≤ 500).

সাবটাস্ক ১ (সর্বোচ্চ ১০ পয়েন্ট)
K = 2

সাবটাস্ক ২ (সর্বোচ্চ ৯০পয়েন্ট)
2 < K ≤ 180

Output

প্রতিটি টেস্টকেসের জন্য k-1 লাইন প্রিন্ট করতে হবে।

প্রতিটি লাইনে দুটি করে সংখ্যা (x,y) থাকবে যা প্রথম রিপিটারের ঘড়ির কাটার বি্পরীত দিকের হিসেবে রিপিটারগুলোর স্থানাঙ্ক প্রকাশ করবে।

1e-6 এর চেয়ে ছোট ভুলকে উপেক্ষা করা হবে।

Samples

Input	Output
1 0 0 1 0 4	0 1 -1 0 0 -1
The image illustrates the position of each repeater.

Input	Output
2 1 0 2 0 2 1 1 2 2 2	0 0 0 0