Emilian is a very smart boy who loves palindromes. Radu knows this fact so he gifted his friend a set of n integers, some being palindromes and other not. Emilian was very happy so he asked himself more questions and he will apriciate if you help him answering one of them. What is the sum of all palindrome integers from the set received from Radu?

**Task**

Given a set of **n** integers calculate the sum of the palindrome integers.

**Input Format**

The first line contains the integer **n** and the second line contains **n**integers.

**Output Format**

The first line contains only one integer representing the sum of all palindrome integers.

**Constraints**

- 1 ≤
**n**≤ 1,000,000 - All integers from the set are less than 1,000,000,000

**Subtasks**

Subtask | Score | Restrictions |
---|---|---|

1 | 15 points | All integers from the set are palindromes |

2 | Another 20 points | All integers from the set are < 100 |

3 | Another 30 points | All integers from the set are < 1000 |

4 | Another 35 points | Normal restrictions |

**Sample Input **

5

1 13 22 121 45

**Sample Output**

144

** Maximum time of execution: 0.6 sec/test.
Maximum available memory: 64 MB **

Adrian the 3^{rd} is a wizard prince. On International Wizard’s Day (4^{th} of November) he
wanted to impress Norela, his dream girl. He has **n** playing cards, which are initially put with the
face down on a table. Adrian can use **m** spells, a spell has the format: **q a1 a2 … aq** . If Adrian uses
a spell, the playing cards with the indices **a1 a2 … aq** will be turned in order. (Integers **a1 a2 … aq**
are all different). The card will be turn face up if it is face down and will be turned face down if it
is face up and all spells can be used no more than one time. Help Adrian impress Norela before his
nemesis Manea Long Eyebrow does it!

**Task**

**Input Format**

**Output Format**

The first line will contain only one integer representing the minimum number of used spells
and the second line will contain the indices of those spells. If there are more solutions with
minimum number of used spells, there will be printed the **minimum lexicographical answer.**

**Subtasks**

**A set of integers a1 a2 … an is lexicographically smaller than other set b1 b2 … bn if there is a k between 1 and n so that a1=b1 , a2=b2 ,.. , ak-1 = bk-1 si ak < bk.**

**Subtasks**

Subtask | Score | Restrictions |
---|---|---|

1 | 20 points | n ≤ 40 m ≤ 18 |

2 | Another 30 points | n ≤ 50 m ≤ 21 |

3 | Another 25 points | n ≤ 60 m ≤ 22 |

4 | Another 30 points | n ≤ 60 m ≤ 24 |

**Sample Input **

5 6

3 1 3 4

2 3 5

2 2 3

3 1 2 5

1 1

4 1 2 3 4

**Sample Output**

3

1 2 3

**Using the spells with indices 1,2 and 3 (1 3 4, 3 5 and 2 3) will turn all cards face up.
It can be observed that another solution that turns all cards face up is 1,4 and 5, but this
one is lexicographically bigger.**

** Maximum time of execution: 0.6 seconds/test.**

**Maximum available memory: 512 MB**

Florin is again in Drobeta-Turnu Severin. Unfortunately, he did not get rid off the
pickpockets that bother him so much! They followed him even in this beautiful city! But Florin is
very smart and figured out how to get rid of them. Drobeta-Turnu Severin is a city that is
represented by a** directed acyclic graph** with **n** vertices and **m** edges. To finally get rid of those
annoying pickpockets, Florin(**who is initially in vertex 1**) has to **reach vertex n** using a certain
path. He managed to obtain a list of p vertices. In his way from vertex 1 to vertex n he has to cross
all these p nodes in the given order, or else he will not get rid of the pickpockets and our hero will
be very upset.

**Task**

Find the number of possible paths from vertex 1 to vertex n that cross all **p** vertices in the
given order from the list. Because the result can be very big you have to print the answer **modulo
1.000.000.007**.

**Input Format**

The first line contains three integers **n**, **m** and **p**.

The second line contains the **p** vertices that have to be crossed by Florin in the given order.

The next **m** lines contain the edges from the graph, represented by two integers **x and y**,
meaning there is an edge from vertex **x** to vertex **y**.

**Output Format**

The first line will contain only one integer representing the number of paths **modulo
1.000.000.007**.

**SUBTASKS**

**WARNING!!! There can be more edges between the same 2 vertices !!!!**

**WARNING!!! It can be observed that at subtask 3, m is bigger than at the subtask. **

**YOU HAVE TO PRINT THE ANSWER MODULO 1.000.000.007.**

**WE HAD NO GOOD REASON TO NAME THIS PROBLEM SHELL **

**Subtasks**

Subtask | Score | Restrictions |
---|---|---|

1 | 10 points | n ≤ 20, m ≤ 190, p ≤ 11 |

2 | Another 45 points | n ≤ 1000, m ≤ 30000, p ≤ 1000 |

3 | Another 20 points | n ≤ 1500, p ≤ 1500 and there is an unique edge
from any vertex x to any vertex y with x ≤ y |

4 | Another 25 points | n , m , p ≤ 1000000 |

**Sample Input **

6 9 3

3 5 6

1 3

1 3

1 2

2 3

2 4

3 4

3 5

4 5

5 6

**Sample Output**

6

**Explanation**

**The 6 paths are:
1-3-5-6
1-3-4-5-6
1-3-5-6
1-3-4-5-6
1-2-3-5-6
1-2-3-4-5-6
It can be observed that 1-3-4-5-6 appears 2 times, this is because there are 2 edges from 1 to
3. One of the paths use an edge, the second one uses the other edge. The same situation is
for 1-3-5-6.
Maximum time of execution: 0.8 seconds/test.
Maximum available memory: 512 MB
**

AlekuKebap is in his math class. While he tries to figure out why 1+1=2, his teacher was
writing on the board a slightly more complicated problem. There are given **Q** queries and a list **S**
with **P** elemnts equal with 0. Let **A** be initially an empty set. The querries can be:

- 0 x (insert value x in set
**A**) - 1 x (erase the value x from set
**A**, it is guaranteed that the value x exists in set**A**)

- Elements form
**A**will be put on distinct standings, the rest being occupied by**P**elements equal with 0 - Let
**S[i]**be a positive element from**S**and**S[j]**the closest positive element from**S**that is located to the left of**S[i]**, then the following condition mus be respected:**i-j ≥ S[i].** - Let
**f**be the first positive element from the left of**S**, then**f ≥ S[f]**.

**Task**

Help AlekuKebap to answer correctly to all teacher’s questions to recive a 10 grade.

**HIS AVERAGE DEPENDS ON THIS GRADE!!
**

**Input Format**

The first line contains two integers **Q** and **P**.

The next **Q** lines contain the description of every query.

**Output Format**

Every line will contain the answer to every question from the **Q** questions.

**SUBTASKS**

**YOU HAVE TO PRINT THE ANSWER MODULO 1.000.000.007.****All numbers that will be added in the set are ≤ 1.000.000.****WARNING!!! If the answer for a query is no, print -1 !!!****WARNING !!!Alecu is not a kebap, he is a human being but this is his name. He is actually a captain…THE CAPTAIN.**

Subtask | Score | Restrictions |
---|---|---|

1 | 10 | Q ≤ 22, P ≤ 22 |

2 | Another 10 points | Q ≤ 100.000, P ≤ 3000 and all the values that will be at the same time in A will be equal |

3 | Another 10 points | Q ≤ 100.000, P ≤ 3000 and all the values that will be at the same time in A will be different |

4 | Another 20 points | Q ≤ 100.000, P ≤ 3000 |

5 | Another 15 points | Q ≤ 100.000, P ≤ 100.000 and all the values that will be at the same time in A will be equal |

6 | Another 15 points | Q ≤ 100.000, P ≤ 100.000 and all the values that will be at the same time in A will be different |

7 | Another 20 points | Q ≤ 100.000, P ≤ 100.000 |

**Sample Input **

**
9 8
0 3
0 3
0 2
1 2
0 1
0 1
0 1
1 3
1 1
**

**Sample Output**

**
6
6
3
6
12
6
-1
60
60
Maximum time of execution: 0.5seconds/test.
Maximum available memory: 512 MB
**

The admission interview at the prestigious University of Cambridge consist of **N** tasks,
numbered from **1** to **N**. Alex is there right now, waiting to attend the interview. Takahiro Wong,
who has just finished his interview, solved all the tasks. More precisely, he solved the **i-th**
problem after **Di** seconds from the beginning of the interview.

Knowing the fact that he can solve the **i-th** problem in **Ti** seconds, Alex asks himself **M**
questions: **x y**. For every question, Alex will consider only the tasks from the interval **[x;y]** and
he wants to know whether he can solve **each of these tasks** before Takahiro Wong. (Alex can
solve the tasks from the interval **[x;y]** in any order).

For example, let’s consider that Alex has to solve the tasks **a** and **b** (in this order). He
will finish task a after **Ta** seconds, and task **b** after **Ta + Tb** seconds. Alex will solve both problems
before Takahiro Wong if **Ta < Da and Ta + Tb < Db**.

Both Takahiro Wong and Alex will start their interviews at second **0**.

Help Alex answer correctly to all **M** questions.

**Standard Input**

- The first line of the standard input will contain
**N**and**M**.

**N**- the number of tasks,**M**- the number of questions. - On the following
**N**lines, there will be**Ti**and**Di**.

**Ti**- the time needed for Alex to solve the**i-th**problem

**Di**- the time (from the beginning of his interview) after Takahiro Wong will solve

the**i-th**problem. - On the following
**M**lines, there will be**x**and**y**, representing the interval**[x; y]**.

**Standard Output**

The standard output will contain **M** lines, the answers to the **M** questions.

The **i-th** line will contain:

**1**, if Alex cand solve all the tasks from the interval**[x;y]**before Takahiro Wond**0**, otherwise.

**Restrictions and SUbtasks**

- 1 ≤ Ti < Di ≤ 10
^{9} - The
**Di**values are not distinct (there can be a value that appears multiple times) - Alex can’t solve 2 tasks in the same time, but Takahiro Wong can (The
**Di**values are not distinct).

**Subtasks**

Subtask | Points | Restrictions |
---|---|---|

1 | 15 points | 1 ≤ N, M ≤ 10 |

2 | 25 points | 1 ≤ N * M ≤ 10^{5} |

3 | 15 points | 1 ≤ N ≤ 10^{3}1 ≤ M ≤ 10 ^{5} |

4 | 45 points | 1 ≤ N , M ≤ 10^{5} |

**Standard Input **

4 3

1 10

14 18

2 7

10 12

3 4

2 4

1 3

**Standard Output**

0

0

1

**Explanation**

The 3rd question refers to the interval **[1;3]**:

- There are 6 ways Alex can solve the tasks: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
- If he solves the tasks in the order (1, 3, 2), we have to fulfill the following

relations:

T1 < D1, T1 + T3 < D3 si T1 + T3 + T2 < D2. We can see that all of them are true. - Because Alex found at least one way to solve all the problems before Takahiro Wong, the answer is 1 for the third question.

Maximum available memory: 256 MB

For a matrix, let’s call a subset of cells, S, connected if there is a path between any two
cells of S which consists only of cells from S. A path is a sequence of cells u1, u2, ..., uk where
ui and ui+1 are adjacent for any **i = 1,k-1**

Given a matrix A with N rows and M columns, we define the following formula for a
connected subset S of A:

**INPUT**

The first line of input contains two number N and M representing the dimensions of the matrix A.

The following N lines describe the matrix. The i-th line contains M integers where the j-th value represents A(i,j).

**OUTPUT**

Print the maximum value of **weight(S)** between all connected components S of the
given matrix.

General constraints

- 0 ≤ A(i,j) ≤ 10
^{9} - 1 ≤ N , M ≤ 10
^{3}

**SUBTASKS**

- For 15 points: 1 ≤ N*M ≤ 20
- For other 15 points: N = 1
- For other 30 points: N,M ≤ 20

**Example**

STANDARD INPUT

2 3

2 4 3

5 7 5

STANDARD OUTPUT

2

__Explanation__

One of the optimal connected subsets is {(1,1),(1,2),(2,2)}. {(1,1),(2,2)} is not a solution because there is no path between (1,1) and (2,2).

Time limit : 0.5seconds

Memory limit : 256MiB

The bipolar monster strikes again! And the peaceful Line city is his target. As the name suggests, Line city consists of 𝑁 neighborhoods numbered 1, 2, 3, … , 𝑁 arranged from left to right in a line.

The bipolar monster makes bipolar operations on the town. An operation consists of choosing a neighborhood X that is not destroyed yet and that is not the leftmost nor the rightmost with this property, with the purpose of destroying it. However, as the monster is bipolar, right after choosing 𝑋, he decides to destroy the 2 yet undestroyed neighborhoods immediate to the left and to the right of 𝑋.

In other words, let’s assume that at some point, the neighborhoods that are not destroyed yet are, in order from left to right 1 ≤ 𝑖1 < 𝑖2 < 𝑖3 < ⋯ < 𝑖𝐾 ≤ 𝑁. X should be one of these neighborhoods, but not the leftmost nor the rightmost. Therefore, 𝑋 = 𝑖𝑗 for 𝑗 with 1 < 𝑗 < 𝐾. For this choice of 𝑗, the monster will destroy the neighborhoods indexed 𝑖𝑗−1 and 𝑖𝑗+1

Our monster is not that much of a monster as you’d think – the 2 of its personalities don’t want to destroy neighborhoods just for fun, they want to make their father proud. The monster knows what exact final configuration of neighborhoods his father would like to see, and so he’d like to make his choices of 𝑋 in such a way that the final configuration of neighborhoods left undestroyed will please his father. His father’s favorite configuration is also a subsequence of the N cities 1 ≤ 𝑝1 < 𝑝2 < 𝑝3 < ⋯ < 𝑝𝑄 ≤ 𝑁.

Sometimes, parents’ expectations are a bit unrealistic, and so can be the case with monsters! It is not even guaranteed that with the given operation (which is the only way the monster can destroy cities, given his bipolarity) the desired subsequence of neighborhoods can be achieved. That’s why the monster would like to know if he can make a proper choice of his moves so that he will achieve the given subsequence. Not only that, but, as you probably guessed, he wants to know a way of doing so, if possible.

You want to help the monster to make his father proud because he’s already been through enough (it’s hard to be a bipolar monster). He will give you a list of several cities similar to Line city and of the configurations his father wants to achieve for each such city (both the configuration and the value of 𝑁 may differ from a city to another). For each city, you need to tell the monster if he can carry out his plan and, if so, how it can do that.

**Input **

On the first line of the input there will be a number 𝑇 – the number of cities the monster is
considering altering in order to make his father proud.
The next 2𝑇 lines contain the description of the cities and monster’s father’s desired final
configuration of the cities, in the following format:

𝑁 𝑄

𝑝_{1}, 𝑝_{2}, … , 𝑝_{q}

This is a communication (interactive) problem!

You did it! You have finally made it to the X spot of the treasure map, but, to open the treasure chest, you first need to break the code. On the label attached to the chest, the rules of the game are written: the code is a binary sequence of length 𝑁, and in order to find this sequence you’re allowed to ask questions of the following type: “is S a subsequence of the hidden sequence?”

A binary sequence 𝑆, with values 𝑆1, 𝑆2, … , 𝑆𝐾 is considered to be a subsequence of the code 𝐶, with values 𝐶1, 𝐶2, … , 𝐶𝑁, if and only if 𝑆 can be obtained by deleting some of the values of 𝐶.

Read more
A D-Balanced Tree (D being a positive integer) is a tree that satisfies the following conditions:

- Each node is either black or white.
- For every black node, there is at least one other black node at distance at most D
- For every white node, there is at least one other white node at distance at most D.

You are given a tree that may not have the colour of every node decided yet. You have to choose the colour of all remaining nodes in order to minimize the value of D. However, there may be no valid positive integer D such that the tree is D-Balanced (see example).

Full score will be given only if you found a valid coloring that leads to your answer. However, partial score may be given otherwise. It will be required to solve the problem for several trees. Read more