• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Two jinns were playing in the sands of Rig-e Jenn. While they laughed and chased after each other, one of them lost its way and may have gotten lost in the salt marshes. The second jinn, worried, goes to find its friend but soon got lost as well. Jeff has divine vision so he will tell you where the two jinns are. Can you guess if they are still together in the same place or they have lost each other in the desert?

input🔗

input consists of one line that contains two names separated by one space and the names of the places of the jinns. each consists of two parts. names can be "Rig-e Jenn" or "salt marshes"

output🔗

your output should consist of one string. "together" if they are in the same place and "lost" if they have lost each other.

example🔗

sample input 1🔗

salt marshes salt marshes

sample output 1🔗

together

sample input 2🔗

salt marshes Rig-e Jenn

sample output 2🔗

lost

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

A bunch of students had booked a train for the SEMANTIC competition. The train consists of several carriages and each carriage has some passengers in it, with a restroom located between each two carriages. There are also restrooms before the first carriage and after the last carriage. After the train stops, suddenly everyone decides to go to the restroom before getting off the train. and long queues have been formed. We know that each person either chooses the restroom on the right or on the left side of their carriage and waits until he/she can go in the restroom. we know each person spends exactly one minute in the restroom. Among all the possible ways that each passenger can choose to stand in one of two adjacent restroom queues, determine the minimum waiting time t for the train that everyone can get off the train after t minutes.

input🔗

the first line consist $n$ the number of train carriages. the next line consist of n numbers. $a_i$ shows the number of passengers in carriage number i.

$1 \le n \le 1000,000$

$1 \le a_i \le 1000,000,000$

output🔗

your output should consist a single number t that shows the minimum waiting time for the train in best case.

example🔗

sample input 1🔗

4
1 2 1 1

sample output 1🔗

1

sample input 2🔗

4
1 2 2 1

sample output 2🔗

2

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Jeff is very indecisive. Whenever an opportunity arises, he rarely decides to pursue it. Each opportunity in Jeff’s life has two characteristics:

$1.$ $V$: the amount of happiness Jeff would gain if he chooses to take this opportunity.

$2.$ $W$: the amount of energy it would cost Jeff to take this opportunity.

Jeff has a limited amount of energy, $K$.

Over $Q$ moments in Jeff's life, opportunities either appear or disappear:

• In the i-th moment, an opportunity with values $V_i$​ (happiness) and $W_i$​ (energy cost) either becomes available or, if it was already available, disappears.

Now, at the end of his life, Jeff is filled with regrets. For each moment $1 \le i \le Q$, he wonders what the maximum happiness he could have achieved would have been if he had chosen to take some of the available opportunities, using no more than his available energy $K$.

Since Jeff doesn’t have the time to solve this problem himself, he’s asking for your help.

input🔗

the first line contains two integers $Q$ and $K$, the number of moments in Jeff's life and the amount of energy Jeff has.

for the next $Q$ lines, the i-th line contains two integers each $V_i$ and $W_i$ the amount of happiness and the energy cost of the opportunity.

if Jeff previously had the opportunity with the same values the opportunity is no longer available otherwise the opportunity becomes available.

$1 \le Q \le 2500$ $0 \le K \le 2500$ $0 \le V_i \le 2500$$1 \le W_i \le 2500$

output🔗

output should contain $Q$ numbers the i-th number should be the maximum amount of happiness Jeff could've achieved if he had chosen to take some of the available opportunities at the i-th moment such that the amount of energy he loses is at most $K$.

example🔗

sample input 1🔗

8 7
4 4
9 2
9 2
7 6
7 6
2 7
4 4
7 4

sample output 1🔗

4
13
4
7
4
4
2
7

• in moment 1 available opportunities are $[(4, 4)]$ Jeff can take opportunity $1$ and gain $4$ happiness
• in moment 2 available opportunities are $[(4, 4), (9, 2)]$ Jeff can take opportunities $1, 2$ and gain $9+4=13$ happiness
• in moment 3 opportunity $(9, 2)$ disappears so opportunities are $[(4, 4)]$ Jeff can take opportunity $1$ and gain $4$ happiness
• in moment 4 available opportunities are $[(4, 4), (7, 6)]$ Jeff can take opportunity $2$ and gain $7$ happiness, he can't take both opportunities since his available energy $K$ is equal to $7$ but taking both opportunities would require energy of at least $7+4=13$

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Jeff got bored in Semnan and decided to pass his time thinking about gcd. We define $gcd(a, b)$ as the greatest common divisor of two natural numbers $a$ and $b$. Jeff defines $F(X, Y)$ between two non empty lists $X_1$, $X_2$, ..., $X_n$ and $Y_1$, $Y_2$, ..., $Y_m$ like this:

$F(X, Y) = max(gcd(X_i, Y_j)) \quad 1 \leq i \leq n, 1 \leq j \leq m$

In other words, $F(X, Y)$ is the greatest gcd between one member of the $X$-list and another member from $Y$-list. if one of the $X$ or $Y$ is empty consider $F(X, Y) = 1$.

Sehri decides to make Jeff's life harder by inserting and deleting numbers in Jeff's lists $Q$ times. more formally for each $1 \le i \le Q$Sehri chooses one of lists $X$ or $Y$ and a number $n_i$, then decides to add $n_i$ to the chosen list or remove one of the occurrences of $n_i$ in the chosen list. After each of Sehri's attempts to make Jeff's life harder, Jeff wonders what is $F(X, Y)$ and since his life is hard enough already, he asks you to calculate $F(X, Y)$ for him. the lists $X$, $Y$ are empty at first. note that it is garanteed that Sehri will always remove an existing $n$.

input🔗

the first line consists $Q$ number of Sehri's attempts. for the next Q lines, i-th line consists of a character '+' or '-' to denote Sehri decided to insert or delete a number. then another character 'X' or 'Y' shows which list Sehri has chosen and then the number $n_i$.

$1 \le Q \le 100,000$

$1 \le n_i \le 1000,000$

output🔗

output should consist of Q number F(X, Y) after each of Sehri's attempts.

example🔗

sample input 1🔗

6
+ X 3
+ Y 1
+ Y 6
+ X 12
- Y 1
+ Y 12

sample output 1🔗

1
1
3
6
6
12

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Jeff and Sehri decided to divide Semnan among themselves. for simplicity let's assume Semnan is a tree consisting of $n$ nodes. A tree with $n$ nodes is a undirected connected graph with with $n - 1$ edges. We also define an array $F$ of length $N$ of integers between 1 to 100,000. Amin gives each of Semnan's tree nodes to either Jeff and Sehri, after Amin divides Semnan each of Jeff or Sehri will have a forest, where forest is a disjoint union of trees. if Jeff's forests consists of $k$ connected components and each of them have $c_1$, $c_2$, ..., $c_k$ number of nodes, his happiness is $\sum_{i=1}^{k} F_{C_i}$

Sehri's happiness is calculated in the same way.

and after that, the amount of happiness of Amin will be the XOR of happiness of Jeff and Sehri. Amin wonders what is the sum of his happiness over all $2^n$ possible divisons of Semnan? Help Amin with this problem.

input🔗

the first line of input consists of the number $n$ the number of nodes in Semnan. the next line will be $n - 1$ numbers $p_2$, $p_3$, ..., $p_n$ where $p_i$ is an edge between node number i and $p_i$. then in the next line there are N numbers denoting array F where the i-th number is $F_i$.

$1 \le n \le 26$ $1 \le p_i \le i + 1$ $1 \le F_i \le 100,000$

output🔗

output should consist of a single number the sum of Amin's happiness over all possible $2^n$ divisions of Semnan.

example🔗

sample input 1🔗

3
1 1
10 5 15

sample output 1🔗

150

• If Jeff gets no nodes Jeff's happiness would be zero but Sehri would get all 3 nodes then Sehri's forest would consist of one component of size 3 then Sehri's happiness would be equal to $F_3=15$ since $15 xor 0 = 15$ Amin's happiness would be equal to 15.
• If Jeff gets one node, Jeff's forest would consist of one connected component of size 1 so Jeff's happiness would be equal to $F_1=10$ but if the node Jeff gets is node number 1 Sehri's forest would consist of 2 connected components of size one so Sehri's happiness would be $F_1+F_1=20$ and Amin's happiness would be $10 xor 20 = 30$ but if Jeff gets is the node 2 or 3 Sehri's forest would consist of one connected component of size 2 so Sehri's happiness would be $F_2=5$ and Amin's happiness would be equal to $10 xor 5 = 15$.
• If Jeff gets two or three nodes it is similar to the previous cases so we have $15+30+15+15+30+15+15+15=150$

sample input 2🔗

5
1 1 2 2
10 2 15 3 1

sample output 2🔗

566

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

The contest area for the programming competition at Semnan University is a convex polygon with $n$ sides. You will be asked $q$ questions. In each question, the coordinates of a student are given, and you need to determine whether the student is inside the contest area or not.

input🔗

The first line of input contains a positive integer $n$, representing the number of vertices of the polygon that defines the contest area in counter clockwise order.

The i-th line of the next $n$ lines contain two integers, $x_i$ and $y_i$, representing the coordinates of i-th vertex of the polygon in order.

The following line contains the integer $q$, indicating the number of students.

again In next $q$ lines, the i-th line contains two integers, $x_i$ and $y_i$, representing the coordinates of a student.

$1 \leq n \leq 10^5$ $1 \leq q \leq 10^6$ $|x_i, y_i| \leq 10^9$

output🔗

For each student, print "IN" if they are within the contest area, or "OUT" if they are not.

example🔗

sample input 1🔗

4
0 0
10 0
10 10
0 10
2
5 5
15 15

sample output 1🔗

IN
OUT

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Two farmers, Ahura and Mazda, want to plant vegetable crops on a shared land. Ahura always plants cucumbers, while Mazda always plants tomatoes.

They divide the land into n separate rectangles, with each rectangle aligned parallel to the $x$ and $y$ coordinate axes. Each of them then marks specific rectangles where they want plant their crops.

Ahura has chosen $n_1$​ rectangles for planting cucumbers, and Mazda has chosen $n_2$​ rectangles for planting tomatoes. we know we cant plant both cucumber and tomato in exactly one place. because of that, After marking their rectangles, they check for any overlapping areas on the land. To avoid conflicts, they agree not to plant anything in these overlapping areas. They will only plant cucumbers and tomatoes in the non-overlapping parts of their designated rectangles.

The goal is to calculate the difference in the area planted by each farmer. Let:

• $S_1$​ represent the total area where Ahura will plants cucumbers,
• $S_2$​ represent the total area where Mazda will plants tomatoes.

Your task is to compute $S_1-S_2$​ and output this value

input🔗

The first line contains a positive integer $n_1$​, the number of rectangles Ahura has chosen for planting cucumbers at first. The next $n_1$​ lines each contains the two opposite corners of each rectangles, $x_1$ and $y_1$, the bottom left corner and then $x_2$ ​, $y_2$​ , representing the upper right corner coordinate of the rectangle designated by Ahura.

The following line contains a positive integer $n_2$​, the number of rectangles Mazda has chosen for planting tomatoes at first. The next $n_2$​ lines each contains the two opposite corners of each rectangles, $x_1$ and $y_1$, the bottom left corner and then $x_2$ ​, $y_2$​ , representing the upper right corner coordinate of the rectangle designated by Mazda.

• It is guaranteed that Ahura's rectangles do not overlap with each other.
• It is guaranteed that Mazda's rectangles do not overlap with each other.

$1 \leq n_1, n_2 \leq 100$ $-1000 \leq x_1 \leq x_2 \leq 1000$ $-1000 \leq y_1 \leq y_2 \leq 1000$

output🔗

Output a single integer, the value of $S_1 - S_2$, which is the difference in the areas of land planted by Ahura and Mazda.

example🔗

sample input 1🔗

1
0 0 10 10
1
5 5 15 15

Ahura and Mazda have overlapping areas in their marked rectangles. Since they avoid planting in these overlapping areas, the non-overlapping areas for both farmers result in an equal area, making S1​−S2​=0.

sample output 1🔗

0

sample input 2🔗

2
0 0 2 4
3 5 4 7
1
1 3 2 9

sample output 2🔗

4

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

A $k$-partition of an array means dividing the array into groups of $k$ elements. The first $k$ elements go in the first group, the next $k$ elements in the second group, and so on... If there are fewer than $k$ elements left at the end, place all remaining elements in the final group.

For example, if the initial array is $[3, 0, 2, 1, 2]$ and $k=2$, the grouping would be $[[3, 0], [2, 1], [2]]$

The score of a group is defined as the bitwise XOR sum of its elements. For example, the score of the group [3,0] is $3$, the score of the group [2,1] is $3$, and the score of the group [2] is $2$. The score of the entire array is the bitwise AND of the scores of all its groups. For the grouping above, the total score of the array is: 3 AND 3 AND 2 = 2.

for each $k$ as $1, 2, 3, ..., n$, calculate the score for a fixed array.

input🔗

The first line of input contains a positive integer n, the number of elements in the array. $1 \leq n \leq 10^6$ The second line contains n integers $a_1, a_2, \dots, a_n\,$ separated by spaces.

$0 \leq a_i \leq 10^9$

output🔗

Print a single line containing the total scores of the array for $k = 1, 2, \dots, n$ separated by spaces.

example🔗

sample input 1🔗

4
1 2 3 4

sample output 1🔗

0 3 0 4

sample input 2🔗

5
3 0 2 1 2

sample output 2🔗

0 2 1 0 2

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

When the server was in serious trouble, Erfan was a great help. Since Erfan is a fan of palindromes, Amin wanted to gift him a palindrome array. However, Erfan felt discouraged by the complexity of that idea and instead requested just a sorted array as a gift.

Initially, you have an array of length $2n$ that consists of $2n$ integers. In each step, you pick the first $n+1$ elements of the array and move them to the end of the array in the same order.

For example, if the initial array is [3, 2, 5, 4, 1, 1], after one step,

it transforms into [1, 1, 3, 2, 5, 4].

Now, Amin wants to know if, after some number of steps, he can sort the array and make Erfan happy, or if Erfan will remain frustrated and never help with another server trouble again.

input🔗

the first line consist $n$ that 2n is the length of the array. the next line consist of $2n$ integers. $a_i$ the array elements.

$1 \le n \le 100,000$

$1 \le a_i \le 1000,000,000$

output🔗

your output should consist one string. "happy erfan" if Amin can sort the array after finite number of steps. "sad erfan" if Amin can't sort the array with any number of steps.

example🔗

sample input 1🔗

2
1 2 3 4

sample output 1🔗

happy erfan

sample input 2🔗

2 
4 3 2 1

sample output 2🔗

sad erfan

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

In Semnan, n houses are arranged in a row. Since everyone doubts that Semnan might be imaginary and doesn’t really exist, Sehri, a famous witch, has hired k experts to verify the existence of the houses in Semnan. The i-th expert has a starting position $ind_i$. where Sehri appears the i-th expert exactly on house $ind_i$. After the starting house is verified by the i-th expert, now they can either see and verify all the houses to the right of them, or all the houses to the left of them. in other words, the i-th expert can verify houses $ind_i, ind_i+1, ..., n$ or verify the the houses $1, 2, ..., ind_i$ note that Sehri will appear experts in different starting houses.

to verify the existence of the i-th house from the right, at least $a_i$ experts must have verify it.

Sehri wants to know if, among all the possible cases where each expert chooses either the left or the right side, there is a situation where we can be sure that all the houses in Semnan exist?

input🔗

the first line consist $n$ and $k$ the number of houses in Semnan that arranged in a row and the number of experts. the next line consist of n numbers. $a_i$ shows the number of experts should verify house number i. then in the next line of the input there is k different numbers ind_i that shows the starting houses.

$1 \le k \le n \le 200,000$ $1 \le a_i \le k$ $1 \le ind_i \le n$

output🔗

your output should consist YES if experts can verify Semnan houses or NO if they cant.

example🔗

sample input 1🔗

7 3
0 0 3 0 3 0 1
3 4 7

sample output 1🔗

NO

sample input 2🔗

7 3
0 0 2 0 3 0 1
3 4 7

sample output 2🔗

YES