Limits 2s, 256 MB

একটা অ্যারে $A$ এর কথা চিন্তা করা যাক যেটা প্রথমে খালি আছে। আমরা অ্যারে তে দুই টাইপের অপারেশন পারফর্ম করবোঃ

  1. অ্যারে এর শেষে একটা এলিমেন্ট $X$ যুক্ত করা।
  2. অ্যারে এর শেষ এলিমেন্ট রিমুভ করা।

এখন অ্যারে এর সবচেয়ে ছোট এলিমেন্ট এবং সবচেয়ে বড় এলিমেন্টের যোগফলকে অ্যারে এর $বিউটি$ $ভ্যালু$ হিসেবে সংজ্ঞায়িত করা যাক। উদাহরণস্বরূপ, ধরি কোনো এক অবস্থাতে অ্যারে $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

Input

প্রথম লাইনে একটা ইন্টিজার $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 (5 পয়েন্ট )

$1 \leq N \leq 10^3$

সাবটাস্ক 2 (15 পয়েন্ট)

$1 \leq N \leq 10^6$

সাবটাস্ক 3 (80 পয়েন্ট)

$1 \leq N \leq 10^7$

Output

প্রতি টেস্টকেসের জন্য তোমাকে একটি লাইন প্রিন্ট করতে হবে, প্রতি অপারেশন এর পরে অ্যারে $A$ এর বিউটি ভ্যালুগুলোর $XOR$ ভ্যালু সেই লাইনটায় লেখা থাকবে।

Sample

InputOutput
1
9
1 2 3 7
12

Initially, V0=2V_0 = 2. By using equation Vi=a×Vi1+c(modm)V_i = a \times V_{i - 1} + c (mod m), V1=5V_1 = 5, It's odd, 5 is added at the back of the array, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V2=1V_2 = 1, it's odd too, 1 is added at the back of the array, hence the array, A=[5,1]A = [5, 1], the beauty value of the array is 1+5=61 + 5 = 6.

V3=4V_3 = 4, it's even, the last element of the array has removed, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V4=0V_4 = 0, it's even too, the last element of the array has removed, hence the array, A=[]A = [], i.e empty, the beauty value of the array is 0+0=00 + 0 = 0.

V5=3V_5 = 3, it's odd, 3 is added at the back of the array, hence the array, A=[3]A = [3], the beauty value of the array is 3+3=63 + 3 = 6.

V6=6V_6 = 6, it's even, the last element of the array has removed, hence the array, A=[]A = [], i.e empty, the beauty value of the array is 0+0=00 + 0 = 0.

V7=2V_7 = 2, it's even too, the array is empty, hence skipped the operation, the beauty value of the array is 0+0=00 + 0 = 0.

V8=5V_8 = 5, it's odd, 5 is added at the back of the array, hence the array, A=[5]A = [5], the beauty value of the array is 5+5=105 + 5 = 10.

V9=1V_9 = 1, it's odd too, 1 is added at the back of the array, hence the array, A=[5,1]A = [5, 1], the beauty value of the array is 1+5=61 + 5 = 6.

XORXOR of all the beauty values of the array after performing each operation is 106100600106=1210 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12. 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.

Submit

Login to submit.

Statistics

56% Solution Ratio
Samin_SieyamEarliest, Jun '20
Sarwar82Fastest, 0.3s
YouKnowWhoLightest, 78 MB
NirjhorShortest, 594B
Toph uses cookies. By continuing you agree to our Cookie Policy.