Next Permutation

$N$ সংখ্যক ভিন্ন ভিন্ন পূর্ণসংখ্যার একটা ধারাকে একটা পারমুটেশন বলা হবে যদি সকল পূর্ণসংখ্যা $1$ থেকে $N$ এর মধ্যে হয়।

একটা পারমুটেশনের যত সংখ্যক জায়গায় একটা উপাদান তার পরের উপাদানের চেয়ে বড় তাকে আমরা ঐ পারমুটেশনের ডিসেন্ট হিসেবে সংজ্ঞায়িত করি। উদাহরণস্বরূপ, $(1, 2, 3, 4, 5)$ পারমুটেশনের ডিসেন্ট $0$, $(4, 2, 1, 3, 5)$ পারমুটেশনের ডিসেন্ট $2$ (যেহেতু $2$ হতেও $4$ বড় এবং $1$ হতেও $2$ বড়), $(5, 4, 3, 2, 1)$ পারমুটেশনের ডিসেন্ট $4$। তাহলে দেখতেই পারছ, $N$ উপাদানের একটা পারমুটেশনের ডিসেন্ট হতে পারে সর্বোচ্চ $N-1$।

তোমাকে $N$ উপাদানের একটা পারমুটেশন $P$ দেওয়া হবে। লেক্সিকোগ্রাফিকালি সবচেয়ে ছোট $N$ উপাদানের সেই পারমুটেশন $Q$ তোমাকে খুঁজে বের করতে হবে যেটা $P$ হতে লেক্সিকোগ্রাফিকালি বড় এবং $Q$ এর ডিসেন্ট $P$ এর ডিসেন্টের সমান হয়। যদি এমন কোন পারমুটেশনের অস্তিত্ব না থাকে, তবে এটা তোমাকে জানাতে হবে।

একটা $N$ উপাদানের পারমুটেশন $A$ আরেকটা $N$ উপাদানের পারমুটেশন $B$ হতে লেক্সিকোগ্রাফিকালি ছোট হবে যদি এমন একটা ইনডেক্স $i$ $(1 \le i \le N)$ এর অস্তিত্ব থাকে যাতে $A_i < B_i$ হয় এবং প্রত্যেক $j$ $(1 \le j \lt i)$ এর জন্য, $A_j = B_j$ হয়। উদাহরণস্বরূপ, $(4, 1, 2, 5, 3)$ হতেও $(3, 4, 1, 2, 5)$ লেক্সিকোগ্রাফিকালি ছোট; $(2, 1, 4, 3, 5)$ হতেও $(2, 1, 3, 5, 4)$ লেক্সিকোগ্রাফিকালি ছোট।

Input

• ইনপুটের প্রথম লাইনে একটা পূর্ণসংখ্যা $T$ দেওয়া থাকে যা টেস্টকেসের সংখ্যা নির্দেশ করে। এরপরে $T$ টেস্টকেসের বর্ণনা রয়েছে।
• প্রত্যেক টেস্টকেসের প্রথম লাইনে একটা পুর্ণসংখ্যা $N$ দেওয়া থাকে।
• দ্বিতীয় লাইনে $N$ সংখ্যক পূর্ণসংখ্যা $P_1,P_2,\dots, P_N$ দেওয়া থাকে।

Constraints

• সাবটাস্ক 1 (3 পয়েন্ট)
  • $1 \le T \le 5×10^5$
  • $1 \le N \le 9$
• সাবটাস্ক 2 (13 পয়েন্ট)
  • $1 \le T \le 10^4$
  • $1 \le N \le 100$
• সাবটাস্ক 3 (27 পয়েন্ট)
  • $1 \le T \le 400$
  • $1 \le N \le 400$
• সাবটাস্ক 4 (16 পয়েন্ট)
  • $1 \le T \le 100$
  • $1 \le N \le 2000$
• সাবটাস্ক 5 (41 পয়েন্ট)
  • $1 \le T \le 50$
  • $1 \le N \le 10^5$

Output

প্রত্যেক টেস্টকেসের জন্য, যদি একটা পারমুটেশন $Q$ এর অস্তিত্ব না থাকে, তবে এক লাইনে পূর্ণসংখ্যা $-1$ প্রিন্ট করতে হবে। অন্যথায়, একটা লাইন প্রিন্ট করতে হবে যেখানে $N$ সংখ্যক স্পেস-দিয়ে-আলাদা-করা পূর্ণসংখ্যা আছে যা $Q$ এর উপাদানগুলো নির্দেশ করে।

Sample

Input	Output
3 3 1 2 3 3 1 3 2 5 5 2 1 3 4	-1 2 1 3 5 2 3 1 4

ইনপুট/আউটপুট ফাইলগুলো বিশাল। দ্রুতগতির IO অপারেশন ব্যবহার কর, যেমন C/C++ এ printf/scanf বা এরকম কিছু।