1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ones and Twos
Contest: CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1700
Tags: binary search, data structures, divide and conquer, math, two pointers

You are given a $$$1$$$-indexed array $$$a$$$ of length $$$n$$$ where each element is $$$1$$$ or $$$2$$$.

Process $$$q$$$ queries of the following two types:

- "1 s": check if there exists a subarray$$$^{\dagger}$$$ of $$$a$$$ whose sum equals to $$$s$$$.
- "2 i v": change $$$a_i$$$ to $$$v$$$.

$$$^{\dagger}$$$ An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 10^5$$$) — the length of array $$$a$$$ and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ is $$$1$$$ or $$$2$$$) — the elements of array $$$a$$$.

Each of the following $$$q$$$ lines of each test case contains some integers. The first integer $$$\mathrm{op}$$$ is either $$$1$$$ or $$$2$$$.

- If $$$\mathrm{op}$$$ is $$$1$$$, it is followed by one integer $$$s$$$ ($$$1 \leq s \leq 2n$$$).
- If $$$\mathrm{op}$$$ is $$$2$$$, it is followed by two integers $$$i$$$ and $$$v$$$ ($$$1 \leq i \leq n$$$, $$$v$$$ is $$$1$$$ or $$$2$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases both do not exceed $$$10^5$$$.

Output format:
For each query with $$$\mathrm{op}=1$$$, output "YES" in one line if there exists a subarray of $$$a$$$ whose sum is equals to $$$s$$$, otherwise output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the first example:

- The answer for the first query is "YES" because $$$a_1+a_2+a_3=2+1+2=5$$$.
- The answer for the second query is "YES" because $$$a_1+a_2+a_3+a_4=2+1+2+1=6$$$.
- The answer for the third query is "NO" because we cannot find any subarray of $$$a$$$ whose sum is $$$7$$$.
- After the fourth query, the array $$$a$$$ becomes $$$[2,1,2,2,2]$$$.
- The answer for the fifth query is "YES" because $$$a_2+a_3+a_4+a_5=1+2+2+2=7$$$.

Example input:
2
5 5
2 1 2 1 2
1 5
1 6
1 7
2 4 2
1 7
3 2
2 2 2
1 6
1 5

Example output:
YES
YES
NO
YES
YES
NO

Editorial:
Permutation Sorting
Contest: CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2100
Tags: data structures, sortings

You are given a permutation$$$^\dagger$$$ $$$a$$$ of size $$$n$$$. We call an index $$$i$$$ good if $$$a_i=i$$$ is satisfied. After each second, we rotate all indices that are not good to the right by one position. Formally,

- Let $$$s_1,s_2,\ldots,s_k$$$ be the indices of $$$a$$$ that are not good in increasing order. That is, $$$s_j < s_{j+1}$$$ and if index $$$i$$$ is not good, then there exists $$$j$$$ such that $$$s_j=i$$$.
- For each $$$i$$$ from $$$1$$$ to $$$k$$$, we assign $$$a_{s_{(i \% k+1)}} := a_{s_i}$$$ all at once.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, find the first time that index $$$i$$$ becomes good.

$$$^\dagger$$$ A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of permutation $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single line containing $$$n$$$ integers where the $$$i$$$-th integer represents the first time that index $$$i$$$ becomes good.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$2$$$ and $$$5$$$ are already in the correct position so indices $$$2$$$ and $$$5$$$ become good at $$$0$$$ second. After $$$1$$$ second, a cyclic shift will be done with $$$s=[1, 3, 4]$$$, resulting in array $$$a=[1, 2, 3, 4, 5]$$$. Notice that indices $$$1$$$, $$$3$$$ and $$$4$$$ become good at $$$1$$$ second.

In the second test case, $$$5$$$ is already in the correct position, so index $$$5$$$ becomes good at $$$0$$$ second. After $$$1$$$ second, a cyclic shift will be done with $$$s=[1, 2, 3, 4, 6]$$$, resulting in array $$$a=[3, 2, 1, 4, 5, 6]$$$. Notice that indices $$$2$$$, $$$4$$$ and $$$6$$$ become good at $$$1$$$ second. After $$$2$$$ seconds, a cyclic shift will be done with $$$s=[1, 3]$$$, resulting in array $$$a=[1, 2, 3, 4, 5, 6]$$$. Notice that indices $$$1$$$ and $$$3$$$ become good at $$$2$$$ second.

Example input:
2
5
3 2 4 1 5
6
2 1 4 6 5 3

Example output:
1 0 1 1 0 
2 1 2 1 0 1

Editorial:
Cyclic Hamming (Hard Version)
Contest: CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3500
Tags: brute force, dp, fft, math, number theory

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$k$$$. You can make hacks only if all versions of the problem are solved.

In this statement, all strings are $$$0$$$-indexed.

For two strings $$$a$$$, $$$b$$$ of the same length $$$p$$$, we define the following definitions:

- The hamming distance between $$$a$$$ and $$$b$$$, denoted as $$$h(a, b)$$$, is defined as the number of positions $$$i$$$ such that $$$0 \le i < p$$$ and $$$a_i \ne b_i$$$.
- $$$b$$$ is a cyclic shift of $$$a$$$ if there exists some $$$0 \leq k < p$$$ such that $$$b_{(i+k) \bmod p} = a_i$$$ for all $$$0 \le i < p$$$. Here $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

You are given two binary strings $$$s$$$ and $$$t$$$ of length $$$2^{k+1}$$$ each. Both strings may contain missing characters (denoted by the character '?'). Your task is to count the number of ways to replace the missing characters in both strings with the characters '0' or '1' such that:

- Each string $$$s$$$ and $$$t$$$ contains exactly $$$2^k$$$ occurrences of each character '0' and '1'
- $$$h(s, c) \ge 2^k$$$ for all strings $$$c$$$ that is a cyclic shift of $$$t$$$.

As the result can be very large, you should print the value modulo $$$998\,244\,353$$$.

Input format:
The first line of the input contains a single integer $$$k$$$ ($$$1 \le k \le 12$$$).

The second line of the input contains string $$$s$$$ of size $$$2^{k+1}$$$, consisting of the characters '0', '1' and '?'.

The third line of the input contains string $$$t$$$ of size $$$2^{k+1}$$$, consisting of the characters '0', '1' and '?'.

It is guaranteed that both strings $$$s$$$ and $$$t$$$ contains no more than $$$2^k$$$ character '0' or '1'.

Output format:
Print a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, we can check that the condition $$$h(s, c) \ge 2^k$$$ for all cyclic shift $$$c$$$ of $$$t$$$ is satisfied. In particular:

- for $$$c = \mathtt{0101}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{0101}) = 2 \ge 2^1$$$;
- for $$$c = \mathtt{1010}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{1010}) = 2 \ge 2^1$$$.

In the second example, there exists a cycle shift $$$c$$$ of $$$t$$$ such that $$$h(s, c) < 2^k$$$ (in particular, $$$c = \mathtt{0011}$$$, and $$$h(s, c) = h(\mathtt{0011}, \mathtt{0011}) = 0$$$).

In the third example, there are $$$2$$$ possible ways to recover the missing characters:

- $$$s = \mathtt{0101}$$$, $$$t = \mathtt{0110}$$$;
- $$$s = \mathtt{0011}$$$, $$$t = \mathtt{0101}$$$.

In the fourth example, there are $$$3$$$ possible ways to recover the missing characters:

- $$$s = \mathtt{00011110}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00011011}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00001111}$$$, $$$t = \mathtt{01010101}$$$.

Example input:
1
0011
0101

Example output:
1

Example input:
1
0011
0110

Example output:
0

Editorial:
Paths on the Tree
Contest: Codeforces Global Round 23
Difficulty rating: 1900
Tags: dfs and similar, dp, greedy, sortings, trees

You are given a rooted tree consisting of $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. You are also given a score array $$$s_1, s_2, \ldots, s_n$$$.

A multiset of $$$k$$$ simple paths is called valid if the following two conditions are both true.

- Each path starts from $$$1$$$.
- Let $$$c_i$$$ be the number of paths covering vertex $$$i$$$. For each pair of vertices $$$(u,v)$$$ ($$$2\le u,v\le n$$$) that have the same parent, $$$|c_u-c_v|\le 1$$$ holds.

It can be shown that it is always possible to find at least one valid multiset. Find the maximum value among all valid multisets.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$1 \le k \le 10^9$$$) — the size of the tree and the required number of paths.

The second line contains $$$n - 1$$$ space-separated integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1\le p_i\le n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th vertex. It is guaranteed that this value describe a valid tree with root $$$1$$$.

The third line contains $$$n$$$ space-separated integers $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \le s_i \le 10^4$$$) — the scores of the vertices.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output format:
For each test case, print a single integer — the maximum value of a path multiset.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one of optimal solutions is four paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, $$$1 \to 4$$$, here $$$c=[4,2,2,2,2]$$$. The value equals to $$$4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54$$$.

In the second test case, one of optimal solution is three paths $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, here $$$c=[3,2,2,1,2]$$$. The value equals to $$$3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56$$$.

Example input:
2
5 4
1 2 1 3
6 2 1 5 7
5 3
1 2 1 3
6 6 1 4 10

Example output:
54
56

Editorial:
Define $$$f(u, cnt)$$$ represents the maximum score of $$$cnt$$$ balls passing through the subtree of node $$$u$$$.
Define $$$num$$$ as the number of the sons of node $$$u$$$. The transition is only related to $$$\lceil cnt / num \rceil$$$ and $$$\lfloor cnt / num \rfloor$$$ two states of the subtree.
For each node $$$u$$$, $$$cnt$$$ can only be two adjacent integer$$$(x, x + 1)$$$.
It can be proved that the four numbers $$$\lfloor x/num \rfloor$$$, $$$\lceil x/num \rceil$$$, $$$\lceil (x/num) \rceil$$$ and $$$\lfloor (x + 1)/num \rfloor$$$ can only have two kinds of numbers at most, and they are adjacent natural numbers.
So the number of states can be proved to be $$$\mathcal{O}(n)$$$.
Carpeting the Room
Contest: Unknown Language Round 3
Difficulty rating: 1100
Tags: *special, implementation

Soroush's room is a square with side length n. Before this contest he bought k fine Persian carpets to carpet his room for celebrating the 100th contest on his favorite site. Each Persian carpet is a square of side length n1.

Soroush wants to cover all the area of his room. Carpets can be put over each other but it is not allowed to rotate the carpets. Can Soroush carpet his room completely?

Input format:
The input consists of three integer numbers n, k and n1 (10 ≤ n ≤ 12, 1 ≤ k ≤ 10, $$\left\lceil \frac{n}{2} \right\rceil \leq n_1 \leq n$$).

Output format:
Write a single YES or NO. Write YES if and only if Sorush can carpet his room completely.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
10 4 6

Example output:
YES

Example input:
10 2 5

Example output:
NO

Editorial:
Friendly Numbers
Contest: Unknown Language Round 3
Difficulty rating: 1500
Tags: *special, implementation

Kiana thinks two integers are friends if and only if one of them divides the other one. For example, 12 and 4 are friends, also 6 and 6 are friends too, but 120 and 36 are not.

A group of non-zero integers is called friendly, if each pair of its integers form a friend pair.

You are given a group of non-zero integers. See if they're friendly.

Input format:
The first line contains n (1 ≤ n ≤ 1000), where n — the number of integers in the group.

The next line contains the elements, sorted in the non-decreasing order. The numbers are comma separated, they have at most 7 digits in their decimal notation and do not have any leading zeros.

Output format:
If the group is friendly write "FRIENDS", else write "NOT FRIENDS".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
1,3,6,12

Example output:
FRIENDS

Example input:
3
1,2,9

Example output:
NOT FRIENDS

Editorial:
A+B
Contest: Unknown Language Round 3
Difficulty rating: 1400
Tags: *special, implementation

Bijan is new to programming. He learned recently that programmers do not code every bit of their apps from scratch.

For example they never write a code to sum two integers, because their languages have the ability to do the sum. But can they use it? Can an experienced coder who has attended more than 100 contests, sum two integers?

Bijan is not sure about this. What's your opinion?

Input format:
You are given two integers a and b, one per line (1 ≤ a, b < 10500). These numbers will not have any leading zeros.

Output format:
Write sum of the two integers. Do not put any leading zeros.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
2
3

Example output:
5

Example input:
1390
2011

Example output:
3401

Editorial:
World of Mouth
Contest: Unknown Language Round 3
Difficulty rating: 1500
Tags: *special, strings

There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made.

She asked n of her friends to help her. They all formed a circle and Aida told the person to her right a piece of news which was just a simple string. Then each person told the string to the person on his/her right. But they didn't tell the string exactly as they'd heard it. Each person made at most one of these two types of changes:

- Removing one character from the end of the heard string.
- Adding a character to the end of the heard string.

Finally when the rumor passed exactly n moves (a complete cycle), Aida heard something quite different from what she expected from the person on her left. She thinks someone has cheated and made some changes other than those explained above. Now she wants you to write a Pike piece of code which gets the initial and final strings and tells Aida whether it's possible to get to the final string from the initial one, by the rules described above.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 8 × 106), the number of Aida's friends. The following two lines contain a non-empty string each — initial and final strings. The lengths of strings are at most 107 and they only contain English alphabet letters.

Output format:
Write a single YES or NO. Write YES only if it's possible to get to the final string from the initial string.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
The input is case-sensitive, while the output is not.

Example input:
100
Codeforces
MMIODPC

Example output:
Yes

Example input:
5
MMIOD
CF

Example output:
No

Editorial:
Lamps in a Line
Contest: Unknown Language Round 3
Difficulty rating: 1600
Tags: *special, math

There are n lamps in a line. The lamps are numbered 1 to n from left to right. There are also n keys. When key number i is pressed, all lamps number x such that i|x change their state.

For two integer numbers a and b, we say a|b if and only if there exists an integer c such that a × c = b.

Amirali likes to play with the keys. He randomly pressed k keys and wants to know the final state of the lamps. Help him by writing a Pike piece of code to solve this task.

Input format:
The first line of input contains a single integer n, the number of lamps (1 ≤ n ≤ 105).

The following line contains n words. The i-th word describes the initial state of lamp number i (see samples for details).

The following line contains a single integer k (1 ≤ k ≤ 104), the number of times a key is pressed. Then in the next line come k integers in range [1, n] which are the numbers of the pressed keys.

Output format:
Write n words to output. Describe the final state of the lamps. See samples for more details.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
off off
2
1 2

Example output:
on off

Example input:
3
off off on
6
1 1 1 1 2 2

Example output:
off off on

Editorial:
Polynom
Contest: Unknown Language Round 3
Difficulty rating: 1800
Tags: *special, implementation

You are given a polynom in form p(x) = (x + a1)·(x + a2)·... (x + an). Write Pike program to print it in a standard form p(x) = xn + b1xn - 1 + ... + bn - 1x + bn. You should write each addend in form «C*X^K» (for example, 5*X^8).

Please, write the polynom in the shortest way, so you should skip unnecessary terms: some terms «C*X^K» should be reduced or even omitted. Look for the samples for clarification.

Input format:
The first line of the input contains n (1 ≤ n ≤ 9). The following n lines contain integer ai ( - 10 ≤ ai ≤ 10).

Output format:
Print the given polynom in a standard way. Note, that the answer in this problem response uniquely determined.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
2
-1
1

Example output:
X^2-1

Example input:
2
1
1

Example output:
X^2+2*X+1

Editorial:
Name the album
Contest: Unknown Language Round 3
Difficulty rating: 1800
Tags: *special, data structures, implementation

The famous singer, Aryo, is going to publish a new album of his great work!

Unfortunately these days, there are many albums, Aryo wants to choose a new name for his album, a name that has not been used or at least has not been used recently.

He has a list of all used album names together with the year the albums were published. He also has a list of suitable names for his album.

If he finds a suitable name which has not been used before, he'll use it. Otherwise he will use the name which was used as long ago as possible. If two such names are found (that haven't been used or were used at the same year), he uses the name that is alphabetically latest.

Help him name his album.

Input format:
The first line contains a single integer n (0 ≤ n ≤ 105), the number of used names.

The following n lines each contain a string (the album name) and an integer (the year album was published). Album names are made of lowercase Latin letters and contain at most 14 letters. The year is in range [1900, 2011].

The following line contains a single integer m (1 ≤ m ≤ 104), the number of suitable album names.

The following m lines each contain a string — a suitable name. It contains at most 14 lowercase Latin letters.

All album names and suitable names are non-empty.

Output format:
Write a single string. The name of the new album.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
3
eyesonme 2008
anewdayhascome 2002
oneheart 2003
2
oneheart
bienbien

Example output:
bienbien

Example input:
2
nasimevasl 2003
basetareha 2006
2
nasimevasl
basetareha

Example output:
nasimevasl

Editorial:
Battleship
Contest: Unknown Language Round 3
Difficulty rating: 2100
Tags: *special, dfs and similar, implementation

Do you know the game Battleship? If no, look into Wikipedia article http://en.wikipedia.org/wiki/Battleship_(game). You are given the positions of ships on a 10 × 10 board for playing Battleship. According to the rules, the board should contain the following ships:

- one of size 4 (4 × 1 or 1 × 4 rectangle),
- two of size 3 (3 × 1 or 1 × 3 rectangles),
- three of size 2 (2 × 1 or 1 × 2 rectangles),
- four of size 1 (1 × 1 rectangles).

The ships should not 'bend', touch each other or overlap in any way. Each ship can be oriented horizontaly or verticaly. Your task is to check whether the given set of boards meets the given conditions.

Input format:
The first line contains number n (1 ≤ n ≤ 10) — the number of boards. Each board is described by 10 lines containing 10 characters each. The symbol "0" stands for an empty square and the symbol "*" stands for a square occupied by a ship. The descriptions of boards are separated with empty lines.

Output format:
Print n lines YES or NO. Print the first word if the board meets the given conditions; otherwise print the second word.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
2
****000000
0000000000
***00***00
0000000000
00000000**
000**00000
00000000**
000*000000
00000*00*0
0*00000000
****000000
0000000000
***00***00
0000000000
00000000**
000**00000
00000000**
0000*00000
00000*00*0
0*00000000

Example output:
YES
NO

Editorial:
Rotation
Contest: Unknown Language Round 3
Difficulty rating: 1500
Tags: *special, geometry, math

Ehsan loves geometry! Especially he likes to rotate points!

Given a point in the plane, Ehsan likes to rotate it by k degrees (counter-clockwise), around the origin. What is the result of this rotation?

Input format:
A single integer k (0 ≤ k < 360) is given in the first line. Two integer numbers x and y are given in the second line ( - 1390 ≤ x, y ≤ 1390).

Output format:
Write two numbers. The result of the rotation. Your answer must have a relative error less than 10 - 1.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
90
1 1

Example output:
-1.00000000 1.00000000

Example input:
180
1 1390

Example output:
-1.00000000 -1390.00000000

Editorial:
Interval Coloring
Contest: Unknown Language Round 3
Difficulty rating: 2400
Tags: *special, greedy, math

Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if there exists no three intervals a, b and c such that the following conditions are satisfied simultaneously:

- a, b and c are colored with the same color,
- $$a \cap b \neq \varnothing$$,
- $$b \cap c \neq \varnothing$$,
- $$a \cap c = \varnothing$$.

Moreover he found out that for every intervals i and j, there is at least one point in i which isn't in j.

Given some set of intervals. You have to find the minimum number k, such that Aryo can find a nice coloring with k colors.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 103), number of intervals.

The following n lines contain a interval description each. Each interval is described by two numbers si, ei which are the start and end points of it ( - 105 < si, ei < 105, si ≤ ei). See samples for clarity. A square bracket stands for including of the corresponding endpoint, while a round bracket stands for excluding.

Output format:
Write a single integer k — the minimum number of colors needed for a nice coloring.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
[1,2)
(3,4]

Example output:
1

Example input:
3
[1,3]
[2,6]
(5,7)

Example output:
2

Editorial: