Hououin Kyouma!

Limits 3s, 512 MB · Interactive

এটি একটি ইন্টারেক্টিভ প্রবলেম !

বিজ্ঞানী ওকাবে রিন্টারো স্টেইন্স গেট আবিষ্কার করার জন্য রাতদিন গবেষণা করছে । বিজ্ঞানী হওয়ার পাশাপাশি সে একজন শিক্ষার্থীও । এজন্য, তাকে অনলাইন ক্লাসে যোগ দিতে হয় । ক্লাস $i$ , $B_ {i}$তম ঘণ্টা এবং $E_i$তম ঘণ্টা ($B_i \leq E_i$) এর মাঝে অনুষ্ঠিত হয় । অর্থাৎ, ক্লাস $i$, $B_i$তম ঘণ্টায় শুরু হয় এবং $E_i$তম ঘণ্টায় শেষ হয় । [বিঃদ্র: $B_i$তম ঘণ্টা এবং $E_i$তম ঘণ্টাও ক্লাসের সময় হিসাবে বিবেচিত ।]

গবেষণা চালিয়ে যেতে, ওকাবের প্রচুর অবসর সময় প্রয়োজন । ক্লাস নেই এমন ঘণ্টাগুলিই অবসর সময় । যেহেতু ওকাবে কোনও বিরতি ছাড়াই অবিচ্ছিন্নভাবে কাজ করতে পছন্দ করে, তাই সে $1^{st}$ ঘণ্টা এবং $T^{th}$ ঘণ্টার মাঝে টানা অবসর সময়ের সর্বোচ্চ পরিমাণ (ঘণ্টায়) নির্ধারণ করতে চায়।

উদাহরণস্বরূপ: ধর, এখানে ক্লাসের সংখ্যা $3$ এবং $T = 11$। ক্লাস $1$ অনুষ্ঠিত হয় $[1, 3]$ ঘণ্টায়, ক্লাস $2$ অনুষ্ঠিত হয় $[4, 5]$ ঘণ্টায় এবং ক্লাস $3$ অনুষ্ঠিত হয় $[9, 9]$ঘণ্টায় । সুতরাং, অবসর সময়গুলো হচ্ছেঃ ঘণ্টা $\{6, 7, 8, 10, 11 \}$ । তন্মধ্যে, একটানা অবসর সময়ের সর্বোচ্চ পরিমাণঃ $3$ ঘণ্টা এবং সময়গুলো হচ্ছেঃ ঘণ্টা $ \{6, 7, 8 \}$ ।

তবে একটি সমস্যা আছে । একটি সংস্থার ষড়যন্ত্রের কারণে, ওকাবে ক্লাস শিডিউলিং সিস্টেমকে শুধুমাত্র ঘণ্টা $[t_1, t_2]$ এর মধ্যকার সর্বমোট অবসর সময়ের পরিমাণ (ঘণ্টায়) জিজ্ঞাসা করতে পারে, যেখানে $1 \leq t_1 \leq t_2 \leq T$। সে বুঝতে পারে যে, সে যা জানতে চায়, তা নির্ধারণ করতে সিস্টেমকে প্রচুর প্রশ্ন জিজ্ঞাসা করতে হবে। তাই, সে তোমাকে "সুপার হ্যাকার" বন্ধু হিসাবে সহায়তা করার আদেশ দিয়েছে ।

Input

প্রথম লাইনে একটি পূর্ণসংখ্যা $C$, টেস্ট কেসের সংখ্যা দেওয়া থাকবে ।
প্রতি টেস্ট কেসের প্রথম লাইনে ক্লাসের সংখ্যা $N$ এবং পূর্ণসংখ্যা $T$ এর মান একটি স্পেস দিয়ে পৃথক করে দেওয়া হবে ।

ইন্টারেকশনের বিবরণঃ

প্রতিটি টেস্ট কেসে, কোনো প্রশ্ন জিজ্ঞাসা করার জন্য, একটি লাইনে "? i j" (কোটেশন চিহ্ন ব্যতীত) প্রিন্ট কর, যেখানে $1 \leq i \leq j \leq T$ । এরপর, প্রশ্নের উত্তর হিসেবে একটি লাইনে একটি পূর্ণসংখ্যা দেওয়া হবে । পূর্ণসংখ্যাটি $ [i, j] $ ঘণ্টার মধ্যকার মোট অবসর সময়ের পরিমাণ (ঘণ্টায়) প্রকাশ করবে ।

তুমি যদি মনে কর, একটানা অবসর সময়ের সর্বোচ্চ পরিমাণ (ঘণ্টায়) নির্ধারণ করতে পেরেছ, তাহল একটি লাইনে "! x" (কোটেশন চিহ্ন ব্যতীত) প্রিন্ট কর, যেখানে $x$ একটানা অবসর সময়ের সর্বোচ্চ পরিমাণকে (ঘণ্টায়) বোঝায় ।

এরপর তুমি একটি লাইনে একটি পূর্ণসংখ্যা $V$ রিড করবে। যদি তোমার ফলাফল সঠিক হয়, তাহলে তুমি $V=1$ পাবে এবং তোমাকে পরবর্তী টেস্ট কেসের জন্য এগিয়ে যেতে হবে । আর যদি এটি শেষ টেস্ট কেস হয়, তাহলে প্রোগ্রাম টার্মিনেট করে দিতে হবে । তোমার ফলাফল ভুল হলে $V=-1$পাবে এবং তোমাকে তোমার প্রোগ্রাম টার্মিনেট করে দিতে হবে ।

তুমি সর্বাধিক $Q$টি প্রশ্ন (উত্তর প্রিন্ট করা বাদে) জিজ্ঞাসা করতে পারবে প্রতিটি টেস্ট কেসে। যদি এর চেয়ে বেশি প্রশ্ন কর বা কোনও ইনভ্যালিড প্রশ্ন জিজ্ঞাসা কর, তবে তুমি প্রশ্নের উত্তর হিসেবে $ -1$ পাবে ।

যে কোনও সময়ে, $-1$ পাওয়ার সাথে সাথে তুমি প্রোগ্রাম টার্মিনেট করবে এবং তখন তোমাকে "Wrong Answer" ভার্ডিক্ট দেওয়া হবে । টার্মিনেট না করলে তুমি যেকোনো ভার্ডিক্ট পেতে পার ("Accepted" ছাড়া) যেহেতু তোমার প্রোগ্রাম এরপরও চলতে থাকবে ।

যেহেতু এটি একটি ইন্টারেক্টিভ প্রবলেম, তাই প্রতিটি লাইন প্রিন্ট করার পর আউটপুট ফ্লাশ করতে ভুলবে না। আউটপুট ফ্লাশ করতে তুমি C++ এ printf এর জন্য fflush(stdout) বা cout এর জন্য cout.flush() ব্যবহার করতে পার, পাইথনের জন্য import sys করে sys.stdout.flush() ব্যবহার করতে পার । তুমি যদি অন্য কোনো প্রোগ্রামিং ভাষা ব্যবহার কর, তবে আউটপুট ফ্লাশ করতে এর ডকুমেন্টেশন দেখ

স্কোরিংঃ

সাবটাস্ক 1 (10 পয়েন্টস):
$1 \leq C \leq 8$
$1 \leq N \leq 300$
$N \leq T \leq 10^{4}$
$Q = 10^4$

সাবটাস্ক 2 (55 পয়েন্টস):
$1 \leq C \leq 8$
$1 \leq N \leq 500$
$N \leq T \leq 10^{15}$
$Q = 5\times10^4$

সাবটাস্ক 3 (35 পয়েন্টস):
$1 \leq C \leq 8$
$1 \leq N \leq 500$
$N \leq T \leq 10^{15}$
$Q = 4.3\times10^4$

তুমি ধরে নিতে পার, সমস্ত ক্লাসের শুরু এবং শেষ সময়, $[1, T]$ ঘণ্টার মাঝে থাকবে এবং একই সময়ে একাধিক ক্লাস নেই ।

Output

ধর, টেস্ট কেসের সংখ্যা, $C=1$ । স্টেটমেন্টের উদাহরণের উপর ভিত্তি করে স্যাম্পল ইন্টারেকশন এরকম হতে পারেঃ

> 1
> 3 11
< ? 2 9
> 3
< ? 6 11
> 5
< ? 1 11
> 5
< ? 7 7
> 1
< ! 3
> 1

> বোঝায় তোমার প্রোগ্রাম কী রিড করবে এবং < বোঝায় তোমার প্রোগ্রাম কী রাইট করবে । এই চিহ্নগুলো বোঝানোর সুবিধার্থে ব্যবহার করা হয়েছে । এরকম চিহ্ন তোমার প্রিন্ট করার দরকার নেই ।

প্রথম প্রশ্নের সময়সীমাঃ ঘণ্টা $[2,9]$ । এই সময়ের মাঝে সর্বমোট অবসর সময়ঃ $3$ ঘণ্টা । ঘণ্টাগুলো হচ্ছেঃ $\{6,7,8\}$ ।
দ্বিতীয় প্রশ্নের সময়সীমাঃ ঘণ্টা $[6,11]$ । এই সময়ের মাঝে সর্বমোট অবসর সময়ঃ $5$ ঘণ্টা । ঘণ্টাগুলো হচ্ছেঃ $\{6,7,8,10,11\}$ ।
তৃতীয় প্রশ্নের সময়সীমাঃ ঘণ্টা $[1,11]$ । এই সময়ের মাঝে সর্বমোট অবসর সময়ঃ $5$ ঘণ্টা । ঘণ্টাগুলো হচ্ছেঃ $\{6,7,8,10,11\}$ ।
চতুর্থ প্রশ্নের সময়সীমাঃ ঘণ্টা $[7,7]$ । এই সময়ের মাঝে সর্বমোট অবসর সময়ঃ $1$ ঘণ্টা । ঘণ্টাটি হচ্ছেঃ $\{7\}$ ।

নোটসঃ
ইন্টারেকটিভ প্রবলেম নিয়ে আরো জানতেঃ https://help.toph.co/toph/interactive-problems