একটা অ্যারে $A$
এর কথা চিন্তা করা যাক যেটা প্রথমে খালি আছে। আমরা অ্যারে তে দুই টাইপের অপারেশন পারফর্ম করবোঃ
$X$
যুক্ত করা।এখন অ্যারে এর সবচেয়ে ছোট এলিমেন্ট এবং সবচেয়ে বড় এলিমেন্টের যোগফলকে অ্যারে এর $বিউটি$
$ভ্যালু$
হিসেবে সংজ্ঞায়িত করা যাক। উদাহরণস্বরূপ, ধরি কোনো এক অবস্থাতে অ্যারে $A$
এর এলিমেন্টগুলো [3, 2, 4]। এখানে সবচেয়ে বড় সংখ্যাটি $4$
এবং সবচেয়ে ছোট সংখ্যাটি $2$
। সুতরাং এই অবস্থাতে অ্যারে এর বিউটি ভ্যালু $2 + 4 = 6$
।
কোনো অবস্থাতে অ্যারে খালি হয়ে গেলে সবচেয়ে ছোট সংখ্যা এবং সবচেয়ে বড় সংখ্যা $0$
ধরতে হবে, অর্থাৎ অ্যারে খালি অবস্থায় এর বিউটি ভ্যালু $0$
। অ্যারে $A$
খালি অবস্থাতে দ্বিতীয় অপারেশন অর্থাৎ শেষ এলিমেন্ট রিমুভ করার অপারেশন আসলে সেটা ইগনোর করতে হবে।
এই সমস্যাতে একাধিক টেস্টকেস থাকবে। প্রতি টেস্টকেসে তোমাকে $N$
টি অপারেশন প্রসেস করতে হবে। প্রতি অপারেশনে অপারেশনের টাইপ দেয়া হবে। অপারেশনটি যদি প্রথম টাইপের হয় তাহলে আরও একটি সংখ্যা $X$
দেয়া হবে, সংখ্যাটি অ্যারে এর শেষে যুক্ত করতে হবে। দ্বিতীয় টাইপের অপারেশন হলে অ্যারে এর শেষ এলিমেন্ট রিমুভ করতে হবে। প্রতি অপারশেন এর পরে তোমাকে অ্যারে $A$
এর $বিউটি$
$ভ্যালু$
বের করতে হবে। সুতরাং তোমার কাছে $N$
টি বিউটি ভ্যালু থাকবে। আউটপুটে সেসব $বিউটি$
$ভ্যালু$
গুলোর $XOR$
(Exclusive OR) প্রিন্ট করতে হবে।
নোটঃ $XOR$
একটি বিটওয়াইজ লজিকাল অপারেশন যেটা দুই ইনপুট ভিন্ন ভিন্ন হলে সত্য রিটার্ন করে। সকল প্রকারের বিট কম্বিনেশন এর জন্য সত্যক সারণি নিচে দেয়া হলোঃ
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
প্রথম লাইনে একটা ইন্টিজার $T$
দেয়া থাকবে, যেটা টেস্টকেসের সংখ্যা নির্দেশ করে।
প্রতি টেস্টকেসের প্রথম লাইনে একটা ইন্টিজার $N$
থাকবে, যেটা অপারেশন এর সংখ্যা নির্দেশ করে। পরবর্তী লাইনে $N$
টি অপারেশন বিস্তারিত দেয়ার পরিবর্তে 4 টি ইন্টিজার $a$
, $b$
, $c$
এবং $m$
দেয়া হবে। তোমাকে নিচের ফর্মুলা ব্যবহার করে কিছু ইন্টিজার $ V_i$
জেনারেট করতে হবে, যেটা $i$
- তম অপারেশন এর টাইপ এবং অপারেশটি প্রথম টাইপের হলে যে ভ্যালুটি নতুন যুক্ত করা লাগবে সেটা দিবে।
$ V_i = a \times V_{i-1} + c \pmod m $
, যেখানে $ V_0 = b$
$ V_i$
বিজোড় হলে তোমাকে অ্যারে এর শেষে $ V_i$
যুক্ত করতে হবে, অর্থাৎ $ X = V_i$
.$ V_i$
জোড় হলে অপারেশনটি দ্বিতীয় টাইপের, তোমাকে অ্যারে এর শেষের এলিমেন্ট টি রিমুভ করতে হবে।
$1 \leq T \leq 10$
$1 \leq a, b, c, m \leq 10^8$
$1 \leq N \leq 10^3$
$1 \leq N \leq 10^6$
$1 \leq N \leq 10^7$
প্রতি টেস্টকেসের জন্য তোমাকে একটি লাইন প্রিন্ট করতে হবে, প্রতি অপারেশন এর পরে অ্যারে $A$
এর বিউটি ভ্যালুগুলোর $XOR$
ভ্যালু সেই লাইনটায় লেখা থাকবে।
Input | Output |
---|---|
1 9 1 2 3 7 | 12 |
Initially, . By using equation , , It's odd, 5 is added at the back of the array, hence the array, , the beauty value of the array is . , it's odd too, 1 is added at the back of the array, hence the array, , the beauty value of the array is . , it's even, the last element of the array has removed, hence the array, , the beauty value of the array is . , it's even too, the last element of the array has removed, hence the array, , i.e empty, the beauty value of the array is . , it's odd, 3 is added at the back of the array, hence the array, , the beauty value of the array is . , it's even, the last element of the array has removed, hence the array, , i.e empty, the beauty value of the array is . , it's even too, the array is empty, hence skipped the operation, the beauty value of the array is . , it's odd, 5 is added at the back of the array, hence the array, , the beauty value of the array is . , it's odd too, 1 is added at the back of the array, hence the array, , the beauty value of the array is . of all the beauty values of the array after performing each operation is . Hence, the answer of testcase 1 is 12. |
টেস্টকেস ১ এর ব্যাখ্যাঃ
শুরুতে, V0 = 2.
Vi = a ✕ Vi - 1 + c (mod m) এই ইকুয়েশন ইউজ করে,
V1 = 5, এটা বেজোড় , অ্যারে এর শেষে 5 এড করা হল। সুতরাং A = [5], অ্যারে এর বিউটি ভ্যালু = 5 + 5 = 10
V2 = 1, এটাও বেজোড় , অ্যারে এর শেষে 1 এড করা হলো। সুতরাং A = [5, 1], অ্যারে এর বিউটি ভ্যালু = 1 + 5 = 6
V3 = 4, এটা জোড়, অ্যারে এর শেষ এলিমেন্ট রিমুভ করা হলো। সুতরাং A = [5], অ্যারে এর বিউটি ভ্যালু = 5 + 5 = 10
V4 = 0, এটাও জোড়, অ্যারে এর শেষ এলিমেন্ট রিমুভ করা হলো। সুতরাং A = [], অর্থাৎ খালি, অ্যারে এর বিউটি ভ্যালু = 0 + 0 = 0
V5 = 3, এটা বেজোড় , অ্যারে এর শেষে 3 এড করা হলো। সুতরাং A = [3], অ্যারে এর বিউটি ভ্যালু = 3 + 3 = 6
V6 = 6, এটা জোড়, অ্যারে এর শেষ এলিমেন্ট রিমুভ করা হলো। সুতরাং A = [], অর্থাৎ খালি, অ্যারে এর বিউটি ভ্যালু = 0 + 0 = 0
V7 = 2, এটাও জোড়, অ্যারে ইতিমধ্যে খালি, তাই অপারেশন টি ইগনোর করা হলো। অ্যারে এর বিউটি ভ্যালু = 0 + 0 = 0.
V8 = 5, এটা বেজোড় , অ্যারে এর শেষে 5 এড করা হল। সুতরাং A = [5], অ্যারে এর বিউটি ভ্যালু = 5 + 5 = 10
V9 = 1, এটাও বেজোড় , অ্যারে এর শেষে 1 এড করা হলো। সুতরাং A = [5, 1], অ্যারে এর বিউটি ভ্যালু = 1 + 5 = 6
প্রত্যেক অপারেশন শেষে পাওয়া সকল বিউটি ভ্যালুগুলোর XOR = 10 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12.
সুতরাং টেস্টকেস ১ এর উত্তর 12.