UTPC Contest 03-01-24 Div. 1 (Advanced)
C. The Corgi Genes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Corgis are interesting. They have genes - but in a world of Corgis, the genes are not expressed by the standard 'ATCG' bases, but rather, there are $$$26$$$ bases, each represented by a unique lowercase English letter.

You, a genetic scientist, are here to understand a corgi's genes. Since genetic diversity is viewed to be beneficial to a corgi's health, you are specifically looking for "interesting" sub-genes (substrings) of a corgi's genes that do not contain more than two of any single gene (letter). You additionally want the sub-genes to be "interesting" – in this case, you want palindrome sub-genes (a palindrome is a string which is read the same forwards as it is backwards).

However, the sub-genes' lengths are quite long, and you are lazy. Develop a program that helps you count the number of distinct "interesting" sub-gene ranges that do not contain more than two of the same gene, given the corgi's gene formation.

Input

One line containing $$$n\ (1\leq n\leq 5\cdot 10^4)$$$ continuous lowercase English letters, representing the gene of the corgi.

Output

A single integer, representing the number of non-empty palindromic sub-genes where no more than two of the same gene is present.

Example
Input
ababa
Output
8
Note

In this case, there are $$$8$$$ distinct ranges that satisfy the "palindrome" and "no more than 2 of each letter" requirements: [1,1]; [2,2]; [3,3]; [4,4]; [5,5]; [1,3]; [2,4]; [3,5].

Observe that [1,5]="ababa" is not valid since it contains 3 instances of the letter a.

D. Dog
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Somewhere in the town of Lean, a highly intelligent Corgi named Dog assists her owner in computer science research. They are currently dabbling in proof verification, where the structure of a proof can be represented as a rooted tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. In this tree, we call root node $$$1$$$ the "goal" and all other nodes as "subgoals" derived from the goal. There is an edge from node $$$a$$$ to node $$$b$$$ if $$$b$$$ is directly derived from $$$a$$$. This time, Dog's owner is working on a peculiar proof.

Example: A proof structure as a rooted tree

This proof is composed of multiple steps.

During a single step of verification, only one leaf node can be solved, and any valid leaf node can be chosen. A leaf node $$$s$$$ that is solved is removed from the tree and the following changes occur:

  • If $$$s$$$ was connected directly to the root node, then no more nodes are generated.
  • Otherwise, among the ancestors of $$$s$$$ , find the one that is directly beneath the root node. The verifier generates two more copies of that ancestor, along with all its children, and connects both of these to the root node.
After the gray node is removed, two copies of the ancestor node and its children are appended to the root node in purple.

Her owner comments that the proof seems endless. However, Dog knows that a proof terminates when there are no more subgoals to solve, i.e. when the tree is reduced to the single root node. In order to ease the burden of her owner's work, Dog wants to figure out the minimum number of steps needed to terminate the proof given the current proof structure. Please help her compute this modulo $$$10^9+7$$$.

Input

The input is a rooted tree describing the current proof structure.

The first line contains an integer $$$n\:(1 \leq n \leq 10^5)$$$.

The next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-$$$th$$$ line contains integers $$$a_i, b_i\: (1 \leq a_i, b_i\leq n; a_i\neq b_i)$$$ — the vertices connected by an edge of the tree.

Output

A single integer representing the minimum number of steps needed to terminate the proof, modulo $$$10^9+7$$$.

Examples
Input
5
1 2
2 3
2 4
1 5
Output
14
Input
7
1 2
2 3
2 4
4 5
4 6
1 7
Output
122
Note

In the first test case, we can do the following,

On step 1, we remove the grey leaf node with no change to the program.

On step 2, we create two purple copies of the subgraph after removing the grey leaf node.

For steps 3-13, we continue choosing a node to remove, and creating two copies of the remaining subgraph.

On step 14, we remove the last leaf node, successfully reaching termination.

E. Colorful Corgis
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Corgi Adoption Center has an adorable selection of corgis with various fur color combinations. Today is adoption day, and they want all of the corgis to be taken home to a loving home. They have gathered them all in a circle to show them all off to their potential new owners. The center has noticed in the past, that no owner likes to have more than 2 distinct fur colors (among their own corgis) in total. Furthermore, in the circle, the corgis are placed next to their friends, and the adoption center wants to avoid separating friends too much. So every individual can adopt a single contiguous segment of the circle. What is the minimum number of compassionate individuals the center needs to guarantee that all corgis are adopted?

Input

The first line will contain a single integer $$$N\ (1 \leq N \leq 10^6)$$$ indicating how many corgis are in the circle. The following $$$N$$$ lines will each contain 1 or 2 lowercase letters indicating the fur colors of each corgi. Note: The $$$n$$$th corgi is next to the $$$1$$$st in the circle.

Output

The output is a single integer indicating the minimum number of individuals needed to adopt all the corgis.

Examples
Input
7
a
b
ab
b
c
d
c
Output
2
Input
6
a
c
d
c
a
b
Output
2
Note

Sample 1:

One person can adopt Corgis 1 - 4 since this has a total of 2 colors: a, b. A second person can adopt Corgis 5 - 7 since this has a total of 2 colors: c, d. Thus, 2 people are needed minimum.

Sample 2:

One person can adopt Corgis 1, 5, and 6 (since the circle wraps around) since this has the 2 colors: a, b. A second person can adopt Corgis 2, 3, and 4 since this has a total of 2 colors: c, d. Thus, 2 people are needed.

F. Walk in the Park
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has started a dog walking service to earn a little extra income! She is able to walk up to 2 dogs a day, 7 days a week. Luckily, Alice has a lot of friends with dogs who need them to be walked on different days of the week and are willing to pay different amounts of money for the job to be completed. Alice has a list of $$$N$$$ friends, who need their dog to be walked for 0 to 7 days of the week. Alice can not choose the same job twice, as her friends only have one dog each. Can you help Alice determine the maximum amount of money she can make a week?

Input

The first line contains an integer $$$N\ (1 \leq N \leq 100)$$$ the number of friends Alice has.

The next $$$N$$$ lines will have eight integers each: the first seven integers will represent the days of the week; a 1 will indicate that the dog needs to be walked on that day and a 0 will indicate the dog does not need to be walked on that day. The eigth integer will be the amount of money, $$$m\ (1 \leq m \leq 10^5)$$$ that the job pays.

Output

Output one integer representing the maximum amount of money Alice can make in a week

Example
Input
4
1 0 1 0 1 0 1 10
0 1 0 1 0 1 0 5
1 1 1 1 1 1 1 100
1 0 0 0 0 0 0 100
Output
205

G. The Great Escape
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At your last Thanksgiving get-together, your clumsy cousin accidentally let your corgi loose in the neighborhood park! The neighborhood park can be modeled as a fenced-in $$$N \times M$$$ square, which we represent as a 2D grid. Your corgi currently occupies the corner (0, 0), and the exit to the park is located at $$$(N, M)$$$.

Your family is interspersed throughout the park at various points $$$(x_i, y_i)$$$. You may call out to any of your family members to help catch your corgi; each family member has some agility $$$r_i$$$. If the corgi enters the circle centered at this person $$$(x_i, y_i)$$$ with radius $$$r_i$$$, then the person can catch the corgi.

Your corgi will attempt to avoid all family members, and cannot escape the park except through the exit. If your corgi manages to make it to the exit $$$(N, M)$$$ without being caught by a family member, then it will escape. What's the minimum number of family members you need to guarantee that your corgi will not escape?

Input

The first line contains three integers $$$N, M, K$$$, where $$$N \times M$$$ $$$(1 \le N, M \le 10^9)$$$ gives the dimensions of the park, and $$$K$$$ $$$(1 \le K \le 10^3)$$$ denotes the number of family members.

The next $$$K$$$ lines each consist of three integers $$$x_i, y_i, r_i$$$ ($$$0 \le x_i \le N, 0 \le y_i \le M, 1 \le r_i \le 10^9$$$) denoting the position $$$(x_i, y_i)$$$ and the agility $$$r_i$$$ of the $$$i$$$th family member.

Output

Output a single integer, the minimum number of family members needed to guarantee that your corgi will not escape, or -1 if it is impossible to guarantee.

Examples
Input
10 8 10
2 2 1
3 5 1
8 2 2
6 7 2
1 2 1
2 6 1
2 2 1
7 5 1
6 4 1
4 0 1
Output
3
Input
8 8 4
2 2 1
3 8 2
1 0 1
3 5 1
Output
1
Note

The first sample test case can be visualized as follows. The green circles represent the family members that should be used to prevent your corgi from escaping.

H. Favorite Treat
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is baking treats for her two corgis, Bob and Charlie!

For some strange reason, Alice has arranged the $$$N$$$ treats she has baked in a tree structure. Each of the $$$N$$$ treats has an associated tastiness, with the $$$i^\text{th}$$$ treat having tastiness $$$t_i$$$.

Bob and Charlie will now play a game as follows:

  • While there are still treats left, Bob will select two treats which are leaves of the tree.
  • Charlie will choose one of the treats to eat, and Bob will be left to eat the other.
  • As the treats are eaten, they, along with their incident edge, are deleted from the graph.

As corgis are known to be extremely clever dogs, Bob and Charlie are both master logicians acting in their own best interest, which is to eat treats with maximum total tastiness. Alice is now curious, just how much will the total tastiness of the treats Bob eats be? Can you help her figure it out?

Input

The first line of input will contain a single integer $$$N\ (2 \leq N \leq 20)$$$, denoting the number of treats Alice has baked. It is guaranteed that $$$N$$$ is even.

The next line will contain $$$N$$$ space-separated integers, $$$t_1, t_2, \dots, t_N\ (1 \leq t_i \leq 2 \cdot 10^9)$$$, denoting the tastiness of each treat.

The following $$$N - 1$$$ lines will each contain two space separated integers $$$u$$$ and $$$v\ (1 \leq u, v \leq N, u \neq v)$$$ indicating that there is an edge between the $$$u^\text{th}$$$ treat and the $$$v^\text{th}$$$ treat. It is guaranteed that these edges form a tree.

Output

Output a single integer denoting the total tastiness of the treats Bob eats, assuming that both he and Charlie act optimally.

Examples
Input
4
1 2 10 100
1 2
3 2
4 2
Output
11
Input
4
1 10 50 100
1 2
3 2
4 2
Output
51
Note

The first sample test case looks like the following:

Optimally, Bob will choose the treats with tastiness 10 and 100 and then the treats with tastiness 1 and 2. Charlie will choose the treats with tastiness 100 and 2, leaving Bob with the treats worth 10 and 1 tastiness, for a total of 11.

The second sample test case looks like the following:

Bob's strategy should now be to choose the treats with tastiness 1 and 10, and then the treats with tastiness 50 and 100. Charlie will choose the treats with tastiness 10 and 100, leaving Bob with the treats worth 1 and 50 tastiness, for a total of 51.

I. Corgi Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is National Welsh Corgi Day, and all the Corgis in Corgistan have gathered in a large grass field. Each Corgi has its own personality, denoted by $$$p_i$$$. You've noticed that the happiness of a pair of Corgis is represent by the bitwise AND of their personalities. Furthermore, a group of Corgis as a total happiness equal to the sum of happiness over all unordered pairs of distinct Corgis. Being enjoyers of counting, the Corgis want to know the sum of happiness over all possible groups they could form amongst themselves. Please help the Corgis by finding this value. Since this value can be enormous, output it modulo $$$998244353$$$.

Formally, you are given $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$. ($$$1 \leq n \leq 2 \cdot 10^5, 0 \leq p_i \lt 2^{22}$$$). For some subset $$$S$$$ of the permutation $$$1, \dots, n$$$, let $$$f(S)$$$ be defined as follows:

$$$$$$f(S) = \sum_{i,j \in S, i \lt j} p_i \& p_j$$$$$$

You must output the sum of $$$f(S)$$$ over all $$$2^n$$$ subsets $$$S$$$, modulo $$$998244353$$$.

Input

The first line of input will contain an integer $$$n$$$, denoting the number of Corgis. ($$$1 \leq n \leq 2 \cdot 10^5$$$) The second line will contain $$$n$$$ space-separated integers $$$p_1 ... p_n$$$, denoting the personalities of the $$$n$$$ Corgis. ($$$0 \leq p_i \lt 2^{22}$$$)

Output

Output the sum of the sum of the bitwise AND of personalities over all unordered pairs of distinct Corgis, for all $$$2^n$$$ subsets of Corgis, modulo $$$998244353$$$.

Examples
Input
3
1 2 3
Output
6
Input
5
3 5 2 1 2
Output
72
Input
6
73283 92928 9211 299 22999 39333
Output
1912096

J1. It's Raining Cats and Corgis (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$x$$$. In this version, $$$x$$$ is always $$$1$$$.

It's raining cats and corgis! ... and a whole bunch of other random animals.

As a zoology-meteorology-geology triple major, you immediately rush to the field to study the phenomenon. The field is an array of $$$N$$$ positions, where the $$$i^{th}$$$ position has elevation $$$h_i$$$.

As you observe the unusual precipitation of animals, you notice that the animals fall from the sky and stack on top of each other. Each animal adds $$$1$$$ unit of elevation to the position where it lands. Animals continue to stack on top of each other until all valleys in the landscape are filled. Formally, a valley exists if there exist positions $$$i, j, k$$$ such that $$$1 \leq i \lt j \lt k \leq N$$$ and $$$h_i \gt h_j \lt h_k$$$ (Visual example provided below).

You wonder that if you increase the height of the landscape at position $$$i$$$ by $$$x$$$ units (where $$$x$$$ is always $$$1$$$), how many animals will fill the resulting landscape.

Input

The first line of input contains 2 space-separated integers $$$N, Q \ (1 \leq N, Q \leq 10^5) - $$$ the size of the landscape and the number of queries to process, respectively.

The second line of input contains $$$N$$$ integers $$$h_i \ (0 \leq h_i \leq 10^5)$$$ separated by spaces, representing the initial elevation at the $$$i^{th}$$$ position in the landscape array.

Each of the following $$$Q$$$ lines contains two integers $$$p_i \ (1 \leq p_i \leq N)$$$ and $$$x_i \ \bf{(x_i = 1)}$$$, representing the position in the landscape array where the elevation will be increased by $$$x$$$ units.

Note: The changes made in each query should be preserved and taken into account when processing subsequent queries.

Output

Please output $$$Q$$$ lines, where the $$$i^{th}$$$ line contains the answer to the $$$i^{th}$$$ query.

Examples
Input
10 4
2 1 4 4 5 2 3 4 5 3
3 1
7 1
4 1
5 1
Output
8
7
6
6
Input
5 4
0 5 0 5 0
2 1
4 1
3 1
1 1
Output
5
6
5
5
Input
6 2
0 0 0 0 0 0
2 1
4 1
Output
0
1
Note

J2. It's Raining Cats and Corgis (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$x$$$. In this version, $$$x$$$ could be up to $$$10^5$$$.

It's raining cats and corgis! ... and a whole bunch of other random animals.

As a zoology-meteorology-geology triple major, you immediately rush to the field to study the phenomenon. The field is an array of $$$N$$$ positions, where the $$$i^{th}$$$ position has elevation $$$h_i$$$.

As you observe the unusual precipitation of animals, you notice that the animals fall from the sky and stack on top of each other. Each animal adds $$$1$$$ unit of elevation to the position where it lands. Animals continue to stack on top of each other until all valleys in the landscape are filled. Formally, a valley exists if there exist positions $$$i, j, k$$$ such that $$$1 \leq i \lt j \lt k \leq N$$$ and $$$h_i \gt h_j \lt h_k$$$ (Visual example provided below).

You wonder that if you increase the height of the landscape at position $$$i$$$ by $$$x$$$ units, how many animals will fill the resulting landscape.

Input

The first line of input contains 2 space-separated integers $$$N, Q \ (1 \leq N, Q \leq 10^5) - $$$ the size of the landscape and the number of queries to process, respectively.

The second line of input contains $$$N$$$ integers $$$h_i \ (0 \leq h_i \leq 10^5)$$$ separated by spaces, representing the initial elevation at the $$$i^{th}$$$ position in the landscape array.

Each of the following $$$Q$$$ lines contains two integers $$$p_i \ (1 \leq p_i \leq N)$$$ and $$$x_i \ (1 \leq x_i \leq 10^5)$$$, representing the position in the landscape array where the elevation will be increased by $$$x$$$ units.

Note: The changes made in each query should be preserved and taken into account when processing subsequent queries.

Output

Please output $$$Q$$$ lines, where the $$$i^{th}$$$ line contains the answer to the $$$i^{th}$$$ query.

Examples
Input
10 4
2 1 4 4 5 2 3 4 5 3
3 1
7 1
4 1
5 1
Output
8
7
6
6
Input
5 4
0 5 0 5 0
2 1
4 1
3 1
1 1
Output
5
6
5
5
Input
6 2
0 0 0 0 0 0
2 1
4 1
Output
0
1
Note