To bid farewell to the final years, their juniors have planned a trip to Topchanchi.
The map of IIT(ISM) Dhanbad can be described as a $$$N*M$$$ grid. The students will be starting their journey from Amber Hostel located at cell ($$$1, 1$$$) via auto. To safely execute their plans they want to reach the main gate (cell ($$$N, M$$$)) without being spotted by Mr. Manohar's secret agents.
Mr. Manohar's office is located at cell ($$$X, Y$$$) and at time $$$t=0$$$ when the auto starts, $$$4$$$ secret agents start from the cell ($$$X$$$, $$$Y$$$) and are supposed to move in $$$4$$$ different directions. If a secret agent hits any wall of the grid, he rebounds to his previous cell and starts walking in the opposite direction. For example, if an agent moving in East direction, is at the cell ($$$1, M$$$) at time $$$t=j$$$, then after a rebound, the secret agent will be at ($$$1, M-1$$$) at $$$t=j+1$$$ and will start moving in the West direction.
At time $$$t=0$$$, $$$Agent$$$ $$$1$$$ goes $$$North$$$, if possible, otherwise $$$South$$$. $$$Agent$$$ $$$2$$$ goes South, if possible, otherwise North. $$$Agent$$$ $$$3$$$ goes East, if possible, otherwise West and similarly for $$$Agent$$$ $$$4$$$.
To pick up the female attendees, the auto has to travel via Ruby Lane (i.e. from the cell ($$$1,1$$$) to ($$$1, M$$$) along the row, then ($$$1, M$$$) to ($$$N, M$$$) along the column) . Traveling across each cell takes $$$1$$$ second time (for both auto and the secret agents).
If at any instant $$$t$$$, both the secret agent and the auto arrive at the same cell, the agent becomes suspicious and the farewell trip plans get spoiled.
Given $$$N$$$, $$$M$$$ and the location of Mr. Manohar's office ($$$X$$$, $$$Y$$$) determine if it's possible to safely reach the main gate.
The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$)
Each of the next $$$T$$$ lines contain four space separated integers $$$N, M, X, Y$$$ $$$(2 \le N \le 10^9$$$, $$$2 \le M \le 10^9$$$, $$$1 \le X \le N$$$, $$$1 \le Y \le M)$$$ denoting the number of rows, number of columns, $$$X$$$-coordinate of Mr. Manohar's office, $$$Y$$$-coordinate of Mr. Manohar's office respectively.
For each test case, print in a newline "Farewell" if their farewell plan will succeed or "BestWishes" if not, without quotes.
2 2 3 2 2 3 3 2 1
BestWishes Farewell
3 100000000 3 50000 2 100000000 3 50000 1 100000000 3 50000 3
BestWishes Farewell BestWishes
Note 1: If the current cell is $$$(i,j)$$$ North cell: $$$(i-1, j)$$$, South cell: $$$(i+1, j)$$$, East cell: $$$(i, j+1)$$$, West cell: $$$(i, j-1)$$$ .
Note 2: Two or more agents and the auto can be in the same cell at any instant t.
Note 3: However, neither any of the agents nor the auto can stay in the same cell for more than one second.
This event, apart from all other consequences, divided the taste of students towards the characters! They began to like the alphabetical symbols alternatively. The first symbol, $$$a$$$ is loved by the juniors while $$$b$$$ by the seniors and $$$c$$$ again by the juniors and so on.
To help things go a little better, one can use the Elegant string. Elegant string can be formed from Special string by performing the following operation any number of times (including 0) on the Special string :
Pick two charcters at adjacent positions such that one of the characters is liked by juniors and the other by seniors and swap them.
Is it possible to obtain the Elegant string from the Special string ?
The first line contains the Special String, and the second line - the Elegant String. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than $$$10^5$$$. The strings have the same length.
Print "Yes" (without the quotes), if it is possible to obtain the Elegant string from the Special string, or "No" (without the quotes) otherwise.
cheel naara
No
potha opath
Yes
The first sample case is obvious.
In the second, p,t and h are liked by seniors while o and a are liked by juniors.
One possible way for converting Special string in Elegant string :
p o t h a $$$\,\to\,$$$ o p t h a
o p t h a $$$\,\to\,$$$ o p t a h
o p t a h $$$\,\to\,$$$ o p a t h
'MID SEM HAI BE MATIYAO', This famous line brought trouble to lots of students in this Semester due to the Covid-19 outbreak.
So, one such student approached his HoD for help. He gave him $$$N$$$, the number of subjects and his marks in each subject, $$$A_i$$$ . The HoD gives him the right to perform the following operation once for every $$$j$$$ = 1 to $$$j$$$ = $$$M$$$ in order, :
Operation: Choose at most $$$B_j$$$ subjects (possibly zero) and replace marks of those subjects to $$$C_j$$$.
Now, he wants to maximize the sum of marks of all the subjects.
As you all know he has done nothing except 'matiyana', in this semester. So he approached you to tell him the maximum sum of the marks of all the subjects, he can get.
The first line contains two integers $$$N$$$, $$$M$$$ (1 $$$\leq$$$ $$$N$$$ , $$$M$$$ $$$\leq$$$ $$$10^5$$$), separated by a space — the number of subjects and the number of operations.
The second line contains $$$N$$$ integers $$$A_i$$$ (1 $$$\leq$$$ $$$A_i$$$ $$$\leq$$$ $$$10^9$$$) separated by spaces — marks in each subject.
The next $$$M$$$ line contain two integers $$$B_j$$$ and $$$C_j$$$ separated by space (1 $$$\leq$$$ $$$B_j$$$ $$$\leq$$$ $$$N$$$, 1 $$$\leq$$$ $$$C_j$$$ $$$\leq$$$ $$$10^9$$$)
Print the maximum possible sum of the marks of all the $$$N$$$ subjects after performing the $$$M$$$ operations
3 2 5 1 4 2 3 1 5
14
10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4
338
3 2 100 100 100 3 99 3 99
300
11 3 1 1 1 1 1 1 1 1 1 1 1 3 1000000000 4 1000000000 3 1000000000
10000000001
In $$$1^{st}$$$ test case, we perform the 2 operations as follows :
a. Choose 0 subjects for the first operation i.e. Don't replace marks in any subject by 3.
b. For the second operation, replace the marks of the $$$2^{nd}$$$ subject by 5
In this way, the sum of the marks of the three subjects becomes 5 + 5 + 4 = 14, which is the maximum result possible.
Lesson : MID SEM MEIN BHI PADH LO THODA
Suddenly, Raju Chacha came to know that the old director DCP, dearly known as Pani, was being transferred back to ISM, within a few days. He became afraid, and decided to levy some charges for using the parent portal to access MIS, to earn a huge revenue till he is present.
Within some time, he came up with an idea and sent the following mail to the student community -
" It has came to my notice that since few days, some mischievous students are accessing the parent portal many times, by means of some script. This is a big no no. Due to this, the network traffic on the parent portal has been increasing exponentially, day by day.
So, from today, a new policy will be implemented to charge the students for using the parent portal, as follows:
(i) Rs. 1 will be charged for using the portal on the first day (today).
(ii) For access to the parent portal on subsequent days, the student will be charged either double or triple of the previous charges, or the charges will be incremented by 1.
i.e. If the student was charged Rs. $$$d_i$$$ on the $$$i^{th}$$$ day, then he would be charged either 2*$$$d_i$$$ , 3*$$$d_i$$$ or 1+$$$d_i$$$ on the $$$(i+1)^{th}$$$ day.
Hope you are enjoying your vacations.
Best Wishes !!"
His main aim was to earn exactly Rs. $$$D$$$ from a single student on a single day. But he wants to do it, in the minimum number of days possible, assuming that there is one student who uses the parent portal daily.
Unfortunately, Raju Chacha doesn't know programming. He needs your help to develop a program which would take the amount $$$D$$$ as input and output the minimum number of days the portal must be accessed (say $$$m$$$) by a student, to earn that amount on a single day.
Along with this, it should also output a sequence of valid charges that should be imposed on each day, so that the charges on the $$$m^{th}$$$ day is Rs. $$$D$$$.
If there are multiple such sequences of length $$$m$$$, you may output any one of them.
The first line of the input contains a single integer $$$T$$$ denoting the number of test cases. The description of $$$T$$$ test cases follows.
The first and only line of each test case contains a single integer $$$D$$$.
1 $$$\leq$$$ $$$T$$$ $$$\leq$$$ $$$10^5$$$
1 $$$\leq$$$ $$$D$$$ $$$\leq$$$ $$$10^6$$$
For each test case, print 2 lines -
The first line containing one integer $$$m$$$ — the minimum number of days, the parent portal must be accessed by a single student, such that he needs to pay Rs. $$$D$$$ on the $$$m^{th}$$$ day.
The second line should contain a sequence of $$$m$$$, integers, representing the charges to be paid on each day.
3 1 5 96234
1 1 4 1 3 4 5 15 1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234
1 1000000
20 1 3 9 27 54 108 216 217 651 1953 3906 7812 15624 15625 31250 62500 125000 250000 500000 1000000
In the first example, $$$D=1$$$ . Since, the initial charge for the $$$1^{st}$$$ day is Rs. 1 itself, so it requires only 1 day, to accomplish the goal.
In the second example, $$$D=5$$$ . Here, we triple the charges for the second day and then increment by 1, for 2 days to achieve the charges of Rs. 5.
Another possibility is to double the charges for 2 days and then increment by 1 on the $$${4^{th}}$$$ day. Hence "1 2 4 5" is also a valid output in this case.
It's Valentine's Day. $$$N$$$ students decided to go for a movie with their partners. But wait! there is a problem, The $$$Dictator$$$ has allotted $$$M$$$ Guards on the way from $$$Ruby$$$ to $$$Main Gate$$$.
Consider the $$$RedCarpet$$$ which is full of $$$Roses$$$ placed from $$$Ruby$$$ to $$$Main Gate$$$ as positive-half of the number line starting with $$$Ruby$$$ at point $$$X$$$ = $$$0$$$ and $$$Main Gate$$$ is at $$$X$$$ = $$$\infty$$$. The $$$i^{th}$$$ Guard has been allotted his duty at the point $$$X_i$$$ during the time interval [$$$L_i-z$$$, $$$R_i-z$$$] where $$$z$$$ is your Luckiness factor [0<$$$z$$$<0.1] and the time starts at $$$t=0$$$.
Now the $$$i^{th}$$$ couple will starting walking at time $$$t$$$ = $$$T_i$$$ from $$$Ruby$$$ towards $$$Main Gate$$$ at speed $$$1$$$ $$$unit/sec$$$. They will not stop until they reach the Main Gate or are caught by any of the guards.
All values in input are integers in the following format –
The first line contains two integers $$$M$$$, $$$N$$$ - the number of $$$Guards$$$ and number of $$$couple$$$.
Each of the following $$$M$$$ lines contains three integers $$$L_i$$$, $$$R_i$$$, $$$X_i$$$($$$1 \leq i\leq M$$$).
Each of next following $$$N$$$ lines contains $$$T_i$$$($$$1 \leq i\leq N$$$).
Input Constraints
$$$1\leq M, N \leq 2 \cdot 10^5$$$
$$$0\leq L_i \lt R_i \leq 10^9$$$
$$$1 \leq X_i \leq 10^9$$$
$$$0 \leq T_1 \lt T_2 \lt ... \lt T_N \leq 10^9$$$
If $$$i \neq j$$$ and $$$X_i = X_j$$$, the intervals [$$$L_i$$$,$$$R_i$$$) and [$$$L_j$$$,$$$R_j$$$) do not overlap.
Print $$$N$$$ lines. If the $$$i^{th}$$$ $$$couple$$$ will be caught by any of the guards, then print the distance covered by them. Otherwise, they will go for the movie, so print $$$-1$$$.
4 6 1 3 2 7 13 10 18 20 13 3 4 2 0 1 2 3 5 8
2 2 10 -1 13 -1
The first couple starts coordinate 0 at time 0 and stop walking at coordinate 2 when reaching a point blocked by the first Guard at time 2.
The second couple starts coordinate 0 at time 1 and reach coordinate 2 at time 3. The first Guard has ended, but the fourth Guard has begun, so this couple also stop walking at coordinate 2.
The fourth and sixth couple encounter no Guard while walking, so they can go for the movie. The output for these cases is $$$-1$$$.
It's $$$Basant$$$, and $$$Sanket$$$ has been searching for a girlfriend from his $$$1^{st}$$$ Year. So this time, he has decided to impress a girl by giving her a $$$Rose$$$.
$$$Roses$$$ can be represented by numbers. From his sources in $$$Rosaline$$$, $$$Sanket$$$ came to know that girls are only impressed by $$$Roses$$$ in which one of the digits is average of all the other digits.
For Example, $$$Rose$$$ number 123, here 2 = $$$\frac{(1+3)}{2}$$$ and contain only specific digits $$$a$$$, $$$b$$$, and $$$c$$$ (Not necessarily all).
Let's call these $$$Roses$$$, Perfect Roses. So, $$$Sanket$$$ went to $$$Hirapur$$$ to buy $$$Roses$$$.
$$$Hirapur$$$ has $$$q$$$ shops ( Numbered 1 to $$$q$$$, as they appear in input ), each shop sells $$$Roses$$$ from number $$$L$$$ to $$$R$$$ (both inclusive). $$$Sanket$$$ is having trouble finding the shop which has the most number of $$$Perfect Roses$$$. Can you help him?
Note 1: 1-Digit numbers (including 0) are not $$$Perfect Roses$$$.
Note 2: Numbers do not contain leading zeros.
The first line of the input contains four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$q$$$ denoting the digits that the girls like (Not necessarily distinct) and the number of shops in $$$Hirapur$$$, respectively. The description of $$$q$$$ shops follows.
The first and only line of each shop contains two integers $$$L$$$ and $$$R$$$ denoting the range of $$$Roses$$$ the shop sells.
0 $$$\leq$$$ $$$a$$$,$$$b$$$,$$$c$$$ $$$\leq$$$ $$$9$$$
1 $$$\leq$$$ $$$q$$$ $$$\leq$$$ $$$10^5$$$
0 $$$\leq$$$ $$$L$$$ $$$\leq$$$ $$$R$$$ $$$\leq$$$ $$$10^9$$$
In 1 line, print the number of the shop that sells the most number of $$$Perfect Roses$$$. If there are multiple such shops, print the one with the minimum shop number.
1 2 3 2 1 100000000 3 19
1
In the given test case $$$Perfect Roses$$$ can be 11,22,33,111,123,132,213,222,231.....
Shop number 1 sells 1637 $$$Perfect Roses$$$, and Shop number 2 sells only 1 $$$Perfect Rose$$$, so the output is 1.
For some unknown (read obvious) reason, most of the students of IIT(ISM) hate a certain someone who is (in)famous for his greeting. Some students took that hate to a different level by forming a secret society. Their society has a network consisting of $$$\textbf{n}$$$ secret offices spread across the campus, numbered $$$\textbf{1}$$$ through $$$\textbf{n}$$$.
There are $$$\textbf{n-1}$$$ secret passages, where each passage connects two offices. The passages are constructed such that every office is reachable from every other office by using some passages. The passages also have a level of security attributed to them. The members of this society only discuss in one of their secret offices. To make things fair between every office, a meeting takes place at each office exactly once.
To attend a meeting to be held at office $$$\textbf{u}$$$, representatives from every other vertex will reach $$$\textbf{u}$$$ by following the shortest path to $$$\textbf{u}$$$. The representatives are smart, so they will hide the information gained in a meeting in the passage with highest level of security on their way back to their respective offices. If there are multiple such passages with highest security level, a copy of the information will be hidden in each passage.
The leader of the society wants a quick overview of all the meetings (one meeting held at each office). Since he is busy spending most of his time protecting the society from that certain someone, he only views informations in the passages where maximum number of informations ( copies are also genuine informations) are hidden. He considers those passages $$$\textbf{most informative passages}$$$. Since, you are also a member (don't worry if you are not a member yet, the legend of IIT(ISM) says that you'll willingly join soon), help your leader find the number of informations hidden in the most informative passage and also the number of such passages.
The first line of the input consists of a single integer $$$\textbf{n}$$$ (2 $$$\leq$$$ $$$n$$$ $$$\leq$$$ 2$$$\cdot$$$10$$$^{5}$$$), the number of secret offices.
Each of the next $$$\textbf{n-1}$$$ lines consists of 3 integers $$$\textbf{u}$$$, $$$\textbf{v}$$$ and $$$\textbf{w}$$$, which means there is a secret passage between offices numbered $$$u$$$ and $$$v$$$ (1 $$$\leq$$$ $$$u$$$,$$$v$$$ $$$\leq$$$ $$$n$$$ and $$$u$$$ $$$\neq$$$ $$$v$$$) and has a security level $$$w$$$ (1 $$$\leq$$$ $$$w$$$ $$$\leq$$$ 10$$$^{9}$$$).
Output consists of two lines.
In the first line print two integers $$$\textbf{m}$$$ and $$$\textbf{k}$$$, number of informations hidden in the most informative passage and the number of such passages respectively.
In the second line print a list of $$$\textbf{k}$$$ integers which are the most informative passages $$$\textbf{sorted}$$$ in increasing order, the passages are numbered $$$\textbf{1}$$$ through $$$\textbf{n-1}$$$ in the order they appear in the input.
3 2 1 3 3 1 1
4 1 1
5 2 1 3 4 3 1 5 4 1 2 3 1
8 2 1 2
Information will be hidden in passage $$$(1,2)$$$ $$$4$$$ times. Once for meeting at $$$3$$$(by representative of $$$2$$$), once for meeting at $$$1$$$(by representative of 2), and twice for meeting at $$$2$$$(by representatives of both $$$1$$$ and $$$2$$$). Since this passage appears first in the input it is numbered $$$1$$$.
For passage $$$(1,3)$$$, infromation is hidden twice. Once for meeting at $$$1$$$(by representative of $$$3$$$) and once for meeting at $$$3$$$(by representative of $$$1$$$). This edge is numbered $$$2$$$.
Since more information is hidden in passage numbered $$$1$$$, it is the most informative passage and it has $$$4$$$ hidden information.
In the second example, both the passages $$$(1,2)$$$ and $$$(3,4)$$$ have maximum number of hidden information($$$8$$$). Hence, both are considered most informative passages.
Assuming, Geek has become the new sexy, The ultimate geeks of the class of 2020 (with high packages) decided to come up with an algorithm which can find the list of girls who would be their potential gfs/bfs (Some Boys might be interested in other boys). Due to limited time, They decided to find the girl with the maximum beauty.
Now, there is a problem, The coders follow the BroCode which clearly states that "A Bro can't try on a girl , another bro is trying on "
According to the algo, All the students can be represented as a tree rooted at node $$$1$$$ with the nodes being the students and the weights their beauty such that the subtree of each boy is the list of potential gfs/bfs.
Note: The subtree of one bro can contain the subtree of other bros
When queried for a Bro, The algo returns the beauty of the most beautiful individual in his subtree. As the Bros have taken an oath to follow the BroCode, For each query, they want to modify the algo in such a way that if a set of other Bros nodes are also given and the algo has to return the beauty of the most beautiful individual excluding the subsequent bros subtree and $$$s_1$$$ himself.
To sum up, A tree rooted at $$$1$$$ of $$$n$$$ nodes is given. there are $$$q$$$ queries such that for each query, a set of numbers from $$$1$$$ to $$$n$$$ is provided. The algo must print the maximum weight in the subtree of first number $$$s_1$$$ excluding the nodes in the subtree of other numbers $$$s_2$$$ onwards.
The first line consists of two integers $$$n$$$(no. of nodes) and $$$q$$$(no. of queries) (1 $$$\leq$$$ $$$n$$$, $$$q$$$ $$$\leq$$$ $$$10^5$$$)
The second line contains $$$n$$$ integers $$$a_1$$$...$$$a_n$$$, where $$$a_i$$$ is the beauty of the $$${i^{th}}$$$ node (0 $$$\leq$$$ $$$a_i$$$ $$$\leq$$$ $$$10^9$$$)
The next $$$n$$$-1 lines contain two integers $$$u$$$ and $$$v$$$ indicating that there lies an edge between $$$u$$$ and $$$v$$$ (1 $$$\leq$$$ $$$u$$$, $$$v$$$ $$$\leq$$$ $$$n$$$)
The next $$$q$$$ lines consists of an integer $$$k$$$ and then $$$k$$$ pairwise distinct integers $$$s_1$$$...$$$s_k$$$ (1 $$$\leq$$$ $$$s_i$$$ $$$\leq$$$ $$$n$$$)
The sum of $$$k$$$ over all queries won't exceed $$$10^5$$$
Output consists of $$$q$$$ lines corresponding to the maximum beauty in the subtree of $$$s_1$$$ excluding the subtrees of $$$s_2$$$... $$$s_k$$$ per query
Print $$$-1$$$ if $$$s_1$$$ itself lies in the subtree of any of $$$s_2$$$...$$$s_k$$$ or excluding $$$s_1$$$ the subtree is empty.
8 4 2 20 4 5 4 10 4 8 1 2 1 3 3 4 4 7 4 8 2 5 2 6 1 4 3 4 1 8 3 4 2 6 2 1 2
8 -1 8 8
In first query,only one input is given, answer= max($$$4$$$,$$$8$$$) = $$$8$$$
In the second query, $$$4$$$ lies in the sub-tree of $$$1$$$ , answer = $$$-1$$$
In the third query, $$$2$$$ and $$$6$$$ aren't a part of the sub-tree of $$$4$$$, so they have no effect on the answer, so answer = max( $$$4$$$,$$$8$$$ ) = $$$8$$$
In the fourth query, $$$2$$$ is a part of sub-tree of $$$1$$$ , so answer excludes the sub-tree of 2, answer= max($$$2$$$, $$$4$$$, $$$5$$$, $$$4$$$, $$$8$$$) = $$$8$$$
Its high time for juniors, as seniors are getting placed one by one and it time for them to ask for a grand treat.
For giving these treats our senior gets happiness score — an integer (maybe negative) number of points. Value for the $$$i^{th}$$$ treat is multiplied by i and are summed up. So, for $$$k$$$ treats with value $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$, the happiness score is
The happiness score is $$$0$$$ if there were no treats were given.
The senior had n juniors asking for a treat and has value $$$s_i$$$ for the $$$i^{th}$$$ of them. He wants to maximize his happiness score and being a competitive programmer he doesn't want to just give it to all of them. He gave himself a problem where he would only give treat to some number of contiguous juniors. More formally, he can cancel any prefix and any suffix of the sequence $$$s_1$$$ , $$$s_2$$$ , ..., $$$s_n$$$. It is allowed to cancel all the treats, or to cancel none of them.
The happiness score is calculated as if there were only non-canceled treats. So, for calculating happiness score he will take summation of the $$$1^{st}$$$ non-canceled one's value multiplied by 1, the $$$2^{nd}$$$ one's value multiplied by 2, and so on, till the last non-canceled junior's treat.
What maximum happiness score can the senior get? He found the problem very challenging so he left it for you to solve. Can you solve it for him?
The first line contains a single integer $$$n$$$ (1 $$$\leq$$$ $$$n$$$ $$$\leq$$$ 2·$$$10^5$$$ ) — the total number of juniors who asked for treat.
The second line contains $$$n$$$ integers $$$s_1$$$ , $$$s_2$$$ , ..., $$$s_n$$$ ( $$$\mid s_i \mid $$$ $$$\leq$$$ $$$10^7$$$ ) — value for corresponding junior.
Print the maximum possible happiness score after all the treats he would possibly give.
6 5 -1000 1 -3 7 -8
16
5 1000 1000 1001 1000 1000
15003
3 -60 -70 -80
0
In the first sample test,our senior should cancel the first two treats, and one last treat. He will be left with juniors with values 1,- 3, 7 what gives him the happiness score= 1·1 + 2·( - 3) + 3·7 = 1 - 6 + 21 = 16.
RD Bhaiya came up with a new digital token system to secure the token numbers for all the customers. The token system is such that whenever he wants to generate some new tokens, he will feed a number into his token machine. The machine will store that number in it, if not already stored.
But these numbers are not the actual token numbers. The actual set of token numbers are the numbers obtained by taking the exclusive-OR ( or XOR $$$\oplus$$$ ) operation of all the subsets of the numbers stored in the machine (the subset may be empty). Now when the customers will reach the shop, they will tell the position of their token number, if all the unique token numbers generated till now, are arranged in increasing order. (This position is known to all the customers via a mobile app, which updates the details as and when the token numbers are updated). So, RD Bhaiya wants to know their actual token number from this position.
When a new customer asks for a token, RD Bhaiya may feed a new number into the machine, so as to increase the number of tokens.
The first line of input contains one integer, $$$q$$$ ( $$$1 \leq q \leq 10^6$$$ ), the number of queries.
Next $$$q$$$ lines contain two integers $$$p$$$ and $$$n$$$, where $$$p$$$ ( $$$1 \leq p \leq 2$$$ ) is query type.
If $$$p=1$$$, $$$n$$$ ($$$1 \leq n \leq 10^9$$$) represents the number that RD Bhaiya feeds into the token machine.
If $$$p=2$$$, $$$n$$$ represents the position of the token and $$$1 \leq n \leq$$$ number of unique token numbers
For the first type of queries don't output anything.
For the second type of queries, output the token number of that customer.
14 2 1 1 1 2 1 2 2 1 2 2 1 2 2 2 3 2 4 1 3 2 1 2 2 2 3 2 4
0 0 1 0 1 2 3 0 1 2 3
Note 1: XOR of an empty subset is 0
Note 2: XOR of a singleton subset is the number present in the subset itself.