Luna and Tina are two final-year IT students at UMT University. In their free time, they came up with the idea of creating a game that simulates the familiar rock-paper-scissors game. This is a strategic game where two players compete against each other using a special deck of cards. The deck consists of ~2n~ cards, divided into three types: rock, paper, and scissors.

Each player is dealt ~n~ cards, and the game proceeds as follows:

• The game consists of ~n~ rounds, and in each round, both players will choose a card from their hand and compare them according to the rules: rock beats scissors, scissors beats paper, and paper beats rock.

• After comparison, if the two cards are equal, neither player scores a point. If one card wins, that player scores 1 point.

• The used card cannot be used again in subsequent rounds.

After developing the game, Luna and Tina decided to test it to find any bugs before release. During the testing, Luna accidentally discovered that he could see the card Tina would choose in each round. Before informing Tina so they could fix the bug together, Luna wanted to surprise Tina with his luck. Therefore, Luna secretly exploited this bug to achieve an overwhelming victory over Tina.

Calculate the maximum point difference between Luna and Tina when the game ends.

Input

The first line is the integer ~n~ ~(1 ≤ n ≤ 10^6)~.

The second line contains ~n~ characters separated by spaces, representing Luna's cards.

The third line contains ~n~ characters separated by spaces, representing Tina's cards.

The second and third lines contain only the characters R, S, and P, corresponding to rock, scissors, and paper, respectively.

Output

A single integer is the maximum point difference between Luna and Tina.

Sample Input 1

3
R P S
P P P

Sample Ouput 1

0

Note

Luna's optimal play strategy:

• Tina chooses the first card P, Luna will choose the card R. Luna loses, so Tina gets 1 point.

• Tina chooses the second card P, Luna will choose the card P. It's a tie, so no one gets any points.

• Tina chooses the last card P, Luna will choose the card S. Luna wins, so Luna gets 1 point.

Thus, the point difference is 1 - 1 = 0.

Given an array ~a~ consisting of ~n~ elements, ~a_1, a_2, . . . , a_n~. Find the maximum value of ~a_i~ mod ~a_j~ with ~1 ≤ i, j ≤ n~ and ~a_i ≥ a_j~.

Input

The first line contains ~a~ positive integer ~n~ ~(n ≤ 10^5)~, which is the number of elements in the array ~a~.

The second line contains ~n~ values ~a_1, a_2,..., a_n~ ~(1 ≤ ai ≤ 10^6)~.

Output

A single integer is the result of the problem

Sample Input 1

9
1 2 3 4 5 6 7 8 9

Sample Ouput 1

4

A company newly founded by Luna. This company, whenever assigned a task, breaks the task down into smaller tasks. One task will be split into many smaller tasks, each with its own completion time. Specifically, there are a total of ~n~ tasks, each task is broken down from exactly one task, and one task can be divided into many smaller tasks (except for task 1). The ~i^{th}~ task has a completion time of ~t_i~ . A task is considered completed when both it and the tasks it was divided into are finished.

Calculate the completion time for all tasks.

Input

The first line contains the integer ~n~ ~(1 ≤ n ≤ 2 · 10^5)~, which is the number of tasks.

The second line contains ~n - 1~ values ~p_2, p_3,... , p_n~, where each ~p_i~ indicates that the ~i^{th}~ task is derived from task ~p_i~ ~(1 ≤ p ≤ n)~.

The third line contains ~n~ values ~t_1, t_2,... , t_n~ ~(t ≤ 10^9)~, which are the completion times for the ~i^{th}~ task.

Output

A single line containing ~n~ values, which are the completion times for the ~i^{th}~ task.

Sample Input 1

5
1 1 2 2
1 1 1 1 1

Sample Ouput 1

5 3 1 1 1

Luna is testing his pathfinding skills in a grid-based navigation challenge. The challenge features a grid with 2 rows and n columns, where Luna's starting position is at the top-left corner, cell (1,1).

In this challenge, Luna's piece can move to any adjacent cell in a single step, including diagonally. Formally, movement from cell ~(x1,y1)~ to cell ~(x2,y2)~ is allowed if ~|x1 - x2| ≤ 1~ and ~|y1 - y2| ≤ 1~. Moving outside the grid boundaries is not permitted.

Certain cells in the grid contain obstacles that cause failure if Luna's piece lands on them. The objective is to navigate from the starting cell to the bottom-right corner of the grid, cell (2,n), without encountering any obstacles.

Your goal is to determine if it is possible for Luna to reach the destination cell given the placement of obstacles.

Input

The first line contains a single integer ~n~ ~(3 ≤ n ≤ 100)~ - the number of columns in the grid.

The next two lines describe the grid. Each of these lines represents one row of the grid - each line consists of characters '0' and '1'. The character '0' indicates a safe cell, while the character '1' indicates a trap cell.

An additional constraint is that cells (1,1) and (2,n) are safe.

Output

Output ~YES~ if it is possible to complete the challenge, and ~NO~ otherwise.

Sample Input 1

6
010101
101010

Sample Ouput 1

YES

Luna is analyzing a set of numbers, consisting of ~n~ integer values. Let ~k~ be the mathematic mean of all the numbers in this set (note that ~k~ may not be an integer).

Luna defines a pair of exception numbers as two values that, when removed from the set, keep the mathematic mean of the remaining ~n - 2~ numbers unchanged at ~k~.

Your task is to determine the number of pairs of indices ~(i, j) (i < j)~ such that removing the numbers at these indices keeps the mathematic mean of the remaining ~n - 2~ numbers equal to ~k~.

The mathematic mean of a set is calculated by dividing the sum of all the numbers by the number of elements.

Input

The first line contains one integer ~n~ ~(3 ≤ n ≤ 2 · 10^5)~ - the number of elements in the array.

The second line contains a sequence of integer ~a_1, a_2,..., a_n~ ~(0 ≤ a_i ≤ 10^9)~, where ~a_i~ is the ~i^{th}~ element of the array.

Output

Print one integer - the number of pairs of positions ~(i, j) i < j~ such that if the elements on these positions are deleted, the mathematic mean of ~n - 2~ remaining elements is equal to ~k~ (that is, it is equal to the mathematic mean of ~n~ elements of the original array ~a~).

Sample Input 1

5
1 4 7 3 5

Sample Ouput 1

2

Note

It is possible to delete the elements on positions 1 and 3, or the elements on positions 4 and 5. ~k = 4~.

As the problem's title suggests, in this task, you are given a value n with the requirement to find the largest prime number ~p~ such that ~n~ is divisible by ~p~.

Input

The single value is ~n~ ~(2 ≤ n ≤ 10^4)~ - representing the value ~n~ in the problem statement.

Output

The single value is the largest prime number ~p~ that satisfies the condition mentioned above.

Sample Input 1

30

Sample Ouput 1

5

In UMT, the students are encouraged to embrace a well-rounded education, combining creativity, technology, and business acumen. One of the traditions at UMT is the "Code Sprint" event, where students compete to solve problems that represent UMT's core values of flexibility, adaptability, and innovation.

Today, you are tasked with a simple yet symbolic problem that captures the essence of UMT's philosophy. The letters "U", "M", and "T" represent three different courses offered at UMT, and students are allowed to take these courses multiple times to become well-rounded professionals. Your task is to count how many times each letter appears in a given sequence of characters..

Input

The first line contains a single integer ~n~ ~(1 ≤ n ≤ 100)~ the number of characters in the sequence.

The second line contains a string of n uppercase English letters.

Output

Print three integers, representing the number of times the characters 'U', 'M', and 'T' appear in the sequence, in that order.

Sample Input 1

7
UMTUMTT

Sample Ouput 1

2 2 3

The stilt game (a type of two-legged crutches) has a race track consisting of two parallel strips of cells (as shown below), each strip containing ~n~ + 2 cells, numbered from 0 (on the left) to ~n~ + 1 (on the right).

Cells from 1 to ~n~ in each strip have an integer written on them. Each player participating in the game uses stilts, starting from cell 0, and continuously moves forward by alternating between two legs, stepping into certain cells, and ending at cell ~n~ + 1. The movement follows these rules:

The left leg must always step into cells on the first strip, and the right leg must step into cells on the second strip.

If one leg has just stepped into cell ~i~ ~(i = 0, 1, . . . , n)~, then on the next step, the other leg can only step into cell ~j~ such that ~i + 1 ≤ j ≤ i + p~, where ~p~ is ~a~ given positive integer no greater than ~n~ (of course, it must also be true that ~j ≤ n + 1;~ ~p~ is referred to as the maximum jump length). The player's game ends when they step into cell ~n~ + 1, which is the last cell on the track. The score that the player receives after the game is the absolute value of the sum of all the numbers from the cells that the player steps on.

Determine the maximum score a player can achieve.

Input

The first line contains two integers ~n~ and ~p~ ~(1 ≤ n ≤ 10^6, 1 ≤ p ≤ n, 1 ≤ p ≤ 50)~.

The second line contains ~n~ integers, which are the numbers written on the cells from the left of the first strip.

The third line contains ~n~ integers, which are the numbers written on the cells from the left of the second strip.

All numbers have an absolute value not exceeding 32,000.

Output

A single value is the answer to the problem.

Sample Input 1

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

Sample Ouput 1

20

Note

The optimal cells to go to are cells (1, 1), (2, 2), (1, 3),(2, 5), (1, 6).

In the Master Chef competition, two talented chefs, Chưng and Quýt, are competing. They are both masters of balancing flavors, but today, they are solving a special challenge using numbers instead of ingredients.

A Taste of the Peak in an array is defined as an element that is greater than both its previous and next elements in array.

Chef Chưng task is to count how many peaks appear in certain parts of the array, while Chef Quýt can modify the array to influence the results for Chưng.

You are given an array 'nums' some queries to help Chef Chưng. You need to process the queries of two types:

• ~1, l, r~: Chef Chưng must determine the number of Taste of the Peak elements in the subarray nums[l..r].
• ~2, p, v~: Chef Quýt changes the element at nums[p] to v,

Input

The first line contains two integers ~n~ and ~q~ with ~(1 ≤ n ≤ 10^5, 1 ≤≤ 10^5)~ being the number of elements in the array and the number of queries

The second line contains n numbers in the array nums with ~(0 ≤ nums[i] ≤ 10^6)~.

The following Q lines each belong to one of the following two categories:

• ~1 l r~: Chef Chưng must determine the number of Taste of the Peak elements in the subarray nums[l..r] with ~(1 ≤ l ≤ r ≤ n)~.
• ~2 p v~: Chef Quýt changes the element at nums[p] to ~v~ with ~(1 ≤ p ≤ n, 0 ≤ v ≤ 10^6)~,

Output

The answer of each type query if it is type 1.

Sample Input 1

6 3
4 1 2 2 1 5
2 3 4
1 1 3
1 1 5

Sample Ouput 1

0
1

Note:

• First we assign nums[3] = 4
• With the query of segment [1, 3] we do not get any valid value
• With the second query of segment [1, 5] we get a satisfying value nums[3]

In the village of Chưng and Quýt, a concert was held, and to make the event vibrant and festive, the villagers used fireflies to illuminate the entire village. Each firefly is placed at a specific location in the village, represented by its coordinates ~(x,y)~. Chưng has placed ~n~ fireflies throughout the village.

Quýt knows that if the positions of any four fireflies form a square, the singer will perform even better. However, after Chưng has decorated the village, Quýt considers moving the fireflies around to optimize the concert's atmosphere. But there's a catch: if there are too many such squares, Quýt becomes lazy and doesn't want to make any changes at all, creating a dilemma.You can look at the picture above to understand better. You are given the coordinates of ~n~ fireflies on the map. Help Quýt determine how many squares can be formed by any set of four fireflies so she can make the right decision.

Input

The first line contains a positive integer ~n~ with ~(1 ≤ n ≤ 10^3)~ being the number of fireflies.

The next n lines each contain 2 numbers ~x, y~ being the coordinates of the fireflies in the village with ~(|x, y| ≤ 10^9)~.*

Output

Number of sets of 4 fireflies forming a square

Sample Input 1

8
2 2
2 4
2 6
4 2
4 4
6 2
6 6
5 5

Sample Ouput 1

2

UMT represents a perfect blend of business, technology, and creativity, driven by the spirit of liberal education. With its ecosystem of international cooperation and comprehensive industry engagement, UMT aims to build a successful and fulfilling academic environment where every student is empowered to reach their full potential. At UMT, students are free to choose their own paths, gaining the flexibility to excel in various professions within a multicultural environment. They are prepared to adapt to the dynamic landscape of the digital age, confidently becoming global citizens, shaping the future, and contributing to their communities.

In the spirit of fostering success, we call on all participants of today's ICPC contest to channel this energy by celebrating UMT! Given a positive integer N, your task is to print the phrase UMT exactly ~N~ times.

Input

• The first line contains a single integer N where ~1 ≤ N ≤ 5 × 10^5~

Output

• N lines each containing a capitalized UMT string

Sample Input 1

3

Sample Ouput 1

UMT
UMT
UMT

Note

We will have symmetrical ice creams: "aa", "baab"and "abaaba".

In city, the company H&M operates ~N~ communication service stations (numbered from 1 to ~N~). To enhance the quality and security of data transmission, each station may have several direct cable connections to other stations. Information can be exchanged between stations bidirectionally via these cables. The communication system of H&M is considered stable if any two stations can exchange information with each other.

After the Aquar storm, some of the cables were severely damaged and need to be replaced. Among these, some cables cross rivers, and replacing them is far more expensive than replacing cables that are on land.

It is known that before the Aquar storm, the system was stable. Your task is to determine the total length of the cables that need to be repaired after the storm. If the system remains stable after the storm, the answer is 0.

Note that your solution should minimize the cost of repairs, giving priority to avoiding river-crossing cables whenever possible (i.e., only replace river-crossing cables if there is no other option).

Input

The first line contains four integers: ~N, M, D,~ and ~R,~ where:

• ~N~ is the number of stations,

• ~M~ is the number of cables,

• ~D~ is the number of damaged cables on land,

• ~R~ is the number of damaged cables that cross rivers.

It is guaranteed that ~0 ≤ N, M ≤ 10^5~ and ~0 ≤ D + R ≤ M~.

The next ~M~ lines describe the ~i^{th}~ cable, each containing three integers: ~u, v,~ and ~l~, which means station u is connected to station v by a cable of length l (1 ≤ l ≤ 1000).

The following ~D~ lines contain the index i of the damaged cables on land ~(1 ≤ i ≤ M)~.

The next ~R~ lines contain the index i of the damaged river-crossing cables ~(1 ≤ i ≤ M)~.

Output

Print the total length of the cables that need to be repaired after the storm

Sample Input 1

5 10 1 7
5 3 2
4 5 9
4 2 4
4 3 1
2 3 1
1 4 5
1 5 4
1 2 7
2 5 8
1 3 9
3
9
6
2
8
4
10
7

Sample Ouput 1

8

Sample Input 1

5 5 2 3
1 2 3
4 5 6
2 3 3
3 4 5
5 1 1
1
2
3
4
5

Sample Ouput 1

13

The city is rolling out a project to expand public spaces by developing parks and squares to improve the quality of life for its residents. As part of the planning process, city officials have pinpointed two key strategic locations on the city map. These two sites, situated along a major roadway, were selected because of their proximity to densely populated neighborhoods and their strong connectivity to main traffic routes. The coordinates of these sites are A~(x1, y)~ and B~(x2, y)~.

In addition to these two strategic points, the city has identified ~n~ potential sites along the Ox axis. These sites are scattered across different areas and were chosen based on their development potential and infrastructure accessibility. City planners aim to combine the two fixed points with two of the ~n~ sites along the Ox axis to form a quadrilateral area, which will then be developed into a large park or public square.

However, to ensure the chosen area meets the development standards, each quadrilateral must have a minimum area of ~S~. Your task is to calculate the total number of ways the city can select sites to form quadrilaterals that meet the area requirement, in order to support the city's public space development plans.

Input

The first line contains two values ~n~ and ~S~ ~(1 ≤ n ≤ 2 · 10^5, 0 ≤ S ≤ 10^9)~ - which represent the number of points on the Ox axis and the minimum area.

The second line contains three integers ~x_1, x_2, y~ ~(1 ≤ x_1, x_2, y ≤ 10^9)~ - representing the coordinates of points ~A~ and ~B~.

The last line contains `~n~ values ~a_0, a_1, ..., a_{n-1}~ ~(1 ≤ ai ≤ 10^9)~ - representing the coordinates of the ~n~ new locations along the Ox axis.

Output

Print a single value, which is the number of ways to select that satisfy the problem's requirements.

Sample Input 1

5 7
1 3 3
1 2 3 4 5

Sample Ouput 1

3

In a small village nestled in the heart of the wilderness, Chưng and Quýt, two close friends, were given an important mission. Their village lies along two large rivers, separating three riverbanks, each numbered from 1 to 3. Their task is to build bridges across the rivers so people can travel from the first bank to the second, and then to the third. Each riverbank has bridge pillars, with each pillar marked by a different symbol.

To build a bridge between two banks, the pillars on both sides must have matching symbols. Importantly, no two bridges are allowed to overlap or cross each other. The question is: How many bridges can Chưng and Quýt build, at most, to connect the first bank to the third?

Input

The first line contains integers ~a_i~ ~(|a_i| < 10^5; 0 < i ≤ 100)~, represents the first bridge pillars.

The second line contains integers ~b_i~ ~(|b_i| < 10^5; 0 < i ≤ 100)~, represents the second bridge pillars.

The third line contains integers ~c_i~ ~(|c_i| < 10^5; 0 < i ≤ 100)~, represents the third bridge pillars.

Output

A single value is the answer to the problem.

Sample Input 1

3 2 1 9 10 3 8 4 9 2 3 4
1 3 2 9 4 2 4 2 3 4 5 2 4
1 3 2 9 3 2 2 4 2 2 9 4 2 3 4 4 2 1

Sample Ouput 1

7

Sample Input 2

2 1 3 5 3 8 5 9 4
1 2 3 4 8 9 12 14
4 1 2 3 4 8 12 9 14 9 2

Sample Ouput 2

4

Chưng is a big fan of cream puffs, and he has created delicious cream puffs for Quýt. Chưng has come up with 26 different flavors of cream puffs, each represented by a lowercase letter (from 'a' to 'z').One day, Chưng successfully made n different cream puffs and planned to bring them over to Quýt's house. However, for Chưng, cream puffs not only have to taste good but also look beautiful. So, he decided to combine consecutive cream puffs into a symmetric cream puff.

A symmetric cream puff is a sequence of consecutive cream puffs with an even length, where the sequence of flavor letters forms a palindromic string. Additionally, another way to create a symmetric cream puff is by combining several smaller symmetric cream puffs in sequence. For example: "aa"and "aabaab"are symmetric cream puffs, but "Quýt"and "Chưng"are not. Since Chưng made too many cream puffs, he doesn't know which symmetric cream puff to give to Quýt. Help him count how many ways he can form symmetric cream puffs using the ~n~ available cream puffs.

Input

• The first line contains a single integer N where 1 ≤ N ≤ 5 × 105, representing the number of cream puffs, numbered from 1 to ~n~.

• The second line contains ~n~ lowercase English letters, where the ~i_{th}~ letter represents the flavor of the ~i_{th}~ cream puff.

Output

• A single line containing the number of ways to form symmetric cream puffs from the given cream puffs.

Sample Input 1

6
abaaba

Sample Ouput 1

3

Note: We will have symmetrical ice creams: "aa", "baab"and "abaaba".