Stick Race

স্কুলে বার্ষিক ক্রীড়া প্রতিযোগিতার সময় চলে এসেছে। এবারের ক্রীড়া প্রতিযোগিতায় কাঠি দৌড় নামে একটি প্রতিযোগিতা থাকছে।

এটা মূলত এমন একটি দৌড় প্রতিযোগিতা যা এক বা একাধিক শিক্ষার্থী দল করে খেলতে পারে। দলের প্রথম শিক্ষার্থী একটি কাঠি হাতে নিয়ে নির্ধারিত স্থান থেকে দৌড় শুরু করে। সে কিছুদূর গিয়ে কাঠি টি তার দলের অন্য শিক্ষার্থীর কাছে দেয়। তখন পরের শিক্ষার্থীটি কাঠি হাতে নিয়ে দৌড় শুরু করে এবং এভাবে চলতে থাকে। এভাবে শেষের শিক্ষার্থী কাঠি হাতে নিয়ে সমাপ্তি রেখা অতিক্রম করলে তার দলের হয়ে দৌড়টি সম্পন্ন হয়।

একটি প্রতিযোগিতায় $R$ সংখ্যক দৌড় সম্পন্ন করতে হয়। প্রত্যেক দৌড় একটি সরলরৈখিক পথ্যে হয়। $i$ তম দৌড়টি সরলরৈখিক পথের $A_i$ স্থান থেকে শুরু হয়ে $B_i$ স্থানে শেষ হয়।

তোমার কাজ হল এই $R$ সংখ্যক দৌড়ের জন্য ভিন্ন ভিন্ন দল গঠন করা। দল গঠনের জন্য তোমার হাতে $M$ সংখ্যক শিক্ষার্থী থাকবে। তুমি একজন শিক্ষার্থী কে একাধিক দলে রাখতে পার। কিন্তু এক দলে এক জন শিক্ষার্থী এক বারের বেশি ব্যাবহার করা যাবে না।

প্রত্যেক শিক্ষার্থীর জনয় আবার কিছু শর্ত আছে।

• $i$ তম শিক্ষার্থী দম ফুরিয়ে যাওয়ার কারণে $S_i$ দূরত্বের বেশি দৌড়াতে পারে না।

• সব শিক্ষার্থীর বাসা দৌড়ানোর সরলরৈখিক পথ্যেই পড়ে। $i$ তম শিক্ষার্থী এই পথের $X_i$ স্থানে থাকে। এবং তাদের বাবা মা তাদেরকে বাসার স্থান ছাড়া অন্ন কোথাও থেকে দৌড় শুরু করতে দিতে চায় না।

  তাই $i$ তম শিক্ষার্থী সবসময় $X_i$ স্থান থেকেই দৌড় শুরু করবে। এবং এক দৌড়ে সে দম ফুরানোর আগ পর্যন্ত যেকোনো দূরত্বে তার দৌড় শেষ করতে পারে।

তোমাকে এখন প্রতি দৌড়ের জন্য একটি করে দল গঠন করতে হবে যেন দলে সম্ভাব্য সবচেয়ে কম শিক্ষার্থী লাগে দৌড়টি সম্পন্ন করতে।

ডেটাসেট এমন ভাবে দেয়া থাকবে যে প্রতি দৌড়ের জন্য কমপক্ষে একটি দল অবশ্যই গঠন করা যায়।

Input

প্রথম লাইনে ২টি পূর্ণসংখ্যা দেয়া থাকবে, $M$ এবং $R$।

পরের $M$ সংখ্যক লাইনে ২টি করে পূর্ণসংখ্যা থাকবে, $X_i$ এবং $S_i$।

পরের $R$ সংখ্যক লাইনে ২টি করে পূর্ণসংখ্যা থাকবে, $A_i$ এবং $B_i$।

Constraints

Subtask 1 (১০ পয়েন্ট)

$1 <= M <= 100000$

$1 <= R <= 10$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

সব শিক্ষার্থীর জন্য $S_i$ এর মান সমান হবে।

Subtask 2 (৪০ পয়েন্ট)

$1 <= M <= 100000$

$1 <= R <= 10$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

Subtask 3 (৫০ পয়েন্ট)

$1 <= M <= 100000$

$1 <= R <= 100000$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

Output

আউটপুটে $R$ সংখ্যক লাইন থাকবে। এদের $i$ তম লাইনে থাকবে $i$ তম দৌড়টি সম্পন্ন করতে সর্বনিম্ন কয়জন লাগে।

Sample

Input	Output
6 2 5 4 8 4 3 4 7 4 10 4 9 4 5 14 3 10	3 2
For the first race, it is 5 -> 9, 9 -> 10, 10 -> 14 The student who lives in 5, goes to point 9, gives to stick to the student who lives in 9. Then that student runs to point 10 and gives the stick to another student who then runs to point 14 to finish the race. For the second race, 3 -> 7, 7 -> 10