Problem Statement

An island country JAGAN in a certain planet is very long and narrow, and extends east and west. This long country is said to consist of two major cultural areas — the eastern and the western. Regions in the east tend to have the eastern cultural features and regions in the west tend to have the western cultural features, but, of course, the boundary between the two cultural areas is not clear, which has been an issue.

You are given an assignment estimating the boundary using a given data set.

More precise specification of the assignment is as follows:

1. JAGAN is divided into $n$ prefectures forming a line in the east-west direction. Each prefecture is numbered 1, 2, ..., $n$ from WEST to EAST.
2. Each data set consists of $m$ features, which has 'E' (east) or 'W' (west) for each prefecture. These data indicate that each prefecture has eastern or western features from $m$ different point of views, for example, food, clothing, and so on.
3. In the estimation, you have to choose a cultural boundary achieving the minimal errors. That is, you have to minimize the sum of 'W's in the eastern side and 'E's in the western side.
4. In the estimation, you can choose a cultural boundary only from the boundaries between two prefectures.

Sometimes all prefectures may be estimated to be the eastern or the western cultural area. In these cases, to simplify, you must virtually consider that the boundary is placed between prefecture No. 0 and No. 1 or between prefecture No. $n$ and No. $n+1$. When you get multiple minimums, you must output the most western (least-numbered) result.

Write a program to solve the assignment.

Input

Each input is formatted as follows:

$n$ $m$
$d_{11}$...$d_{1n}$
...
$d_{m1}$...$d_{mn}$

The first line consists of two integers $n$ ($1 \le n \le 10{,}000$), $m$ ($1 \le m \le 100$), which indicate the number of prefectures and the number of features in the assignment. The following $m$ lines are the given data set in the assignment. Each line contains exactly $n$ characters. The $j$-th character in the $i$-th line $d_{ij}$ is 'E' (east) or 'W' (west), which indicates $j$-th prefecture has the eastern or the western feature from the $i$-th point of view.

Output

Print the estimated result in a line. The output consists of two integers sorted in the ascending order which indicate two prefectures touching the boundary.

Sample Input 1

2 1
WE

Output for the Sample Input 1

1 2

Sample Input 2

3 2
WWE
WEE

Output for the Sample Input 2

1 2

Both estimates "1 2" and "2 3" achieve 1 error as the minimum. From the restriction that you must adopt the most western estimate, you must output "1 2".

Sample Input 3

3 1
WWW

Output for the Sample Input 3

3 4

In this case, all the prefectures are western. As described in the problem statement, you must virtually consider that the boundary is placed between third and fourth prefectures.

Sample Input 4

3 1
WEW

Output for the Sample Input 4

1 2

You cannot assume that 'E's and 'W's are separated.

Problem Statement

In 20015, JAG (Jagan Acceleration Group) has succeeded in inventing a new accelerator named “Force Point” for an experiment of proton collision on the two-dimensional $xy$-plane. If a proton touches a Force Point, it is accelerated to twice its speed and its movement direction is veered. A proton may be veered by a Force Field in four ways: the positive or negative directions parallel to the $x$- or the $y$-axis. The direction in which a proton veers is determined by the type of the Force Point. A Force Point can accelerate a proton only once because the Force Point disappears immediately after the acceleration. Generating many Force Points on the two-dimensional plane, which is called a 2D Force Point Field, allows us to accelerate a proton up to a target speed by sequentially accelerating the proton with the Force Points in the 2D Force Point Filed.

The Force Point generation method is still under experiment and JAG has the following technical limitations:

• JAG cannot generate a Force Point with a specified position and a type.
• JAG cannot generate a Force Point after putting a proton into a 2D Force Point Field.
• JAG cannot move Force Points.
• JAG cannot change a proton's direction except by the effect of Force Points.
• JAG can use only one proton for a 2D Force Point Field.
• JAG can put a proton moving in any direction with its speed 1 at any position in a 2D Force Point Field.

In order to achieve the maximum speed of a proton, the engineers at JAG have to choose the optimal initial position and the optimal initial direction of the proton so that the proton is accelerated by as many Force Points as possible, after carefully observing the generated 2D Force Point Field.

By observing a generated 2D Force Point Field, the number of the generated Force Points is known to be $n$. The position ($x_i$, $y_i$) and the direction veering type $d_i$ of the $i$-th point are also known. Your task is to write a program to calculate the maximum speed of a proton by acceleration on a given 2D Force Point Field when JAG puts a proton optimally.

Input

The input consists of a single test case which describes a 2D Force Point Field in the following format.

$n$
$x_1$ $y_1$ $d_1$
...
$x_n$ $y_n$ $d_n$

The first line contains one integer $n$ ($1\le n\le 3{,}000$) which is the number of the Force Points on the 2D Force Point Field. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10^9$) and one character $d_i$ ($d_i$ is one of '>', 'v', '<' or '^'). $x_i$ and $y_i$ represent a coordinate of the $i$-th Force Point, and $d_i$ is the direction veering type of the $i$-th force point. A force point with a type '>' changes proton’s direction to the positive direction of the $x$-axis, 'v' represents the positive direction of the $y$-axis, '<' represents the negative direction of the $x$-axis, and '^' represents the negative direction of the $y$-axis. You can assume that any two Force Points are not generated on the same coordinates.

Output

Display a line containing the integer $\log_2 v_{\mathrm{max}}$, where $v_{\mathrm{max}}$ is the proton's possible fastest speed.

Sample Input 1

9
0 0 v
1 0 >
2 0 <
0 1 >
1 1 v
2 1 v
0 2 ^
1 2 ^
2 2 <

Output for the Sample Input 1

9

The input looks like the following diagram. All the Force Points will disappear if you put a proton at $(1, 1)$.

v><
>vv
^^<

Sample Input 2

9
0 0 ^
1 0 ^
2 0 ^
0 1 <
1 1 ^
2 1 >
0 2 v
1 2 v
2 2 v

Output for the Sample Input 2

2

Problem Statement

Zephir is an owner of the “kuru kuru sushi” restaurants. In these restaurants, sushis are placed on a rotating circular belt conveyor and delivered to customers.

Zephir owns $n$ restaurants numbered from $0$ to $n-1$. Due to his passion for rotation, these restaurants are placed on the circumference of a circle, and have huge belt conveyors under the ground between adjacent restaurants. One day, the ingredients of sushis were short in some restaurants. Therefore, he decided to transport some ingredient foods between restaurants by using these belt conveyors.

The $i$-th ($0 \leq i \leq n-2$) belt conveyor connects the restaurants $i$ and $i+1$. The $(n-1)$-th belt conveyor connects the restaurants $n-1$ and $0$. The length of the $i$-th belt conveyor is $w_i$. He wants to transport $q$ foods from some restaurants to other restaurants. The $i$-th food should be transported from restaurant $s_i$ to $t_i$.

Zephir wants to minimize the total cost of transportation. The transportation cost of each food can be changed by the settings of the direction of the belt conveyors. Each belt conveyor can transport foods in only a single direction, which can be set by Zephir. Moreover, the settings cannot be changed while transporting all $q$ foods. The transportation cost of the $i$-th food is the sum of the length of the belt conveyors in the shortest path from restaurant $s_i$ to $t_i$. He should set the direction of belt conveyors to transport all foods. Write a program to calculate the minimum value of the total cost, which is the sum of the transportation costs of all the $q$ foods.

Input

Each input is formatted as follows:

$n$ $q$
$w_0$ $w_1$ ... $w_{n-1}$
$s_0$ $t_0$
...
$s_{q-1}$ $t_{q-1}$

The first line contains two integers $n$ and $q$. $n$ ($3 \leq n \leq 10^5$) denotes the number of the restaurants, and $q$ ($1 \leq q \leq 10^5$) denotes the number of the foods to transport. The next line contains $n$ integers. $w_i$ ($1 \leq w_i \leq 10^5$) denotes the length of the $i$-th belt conveyor. Each of the following $q$ lines contains two integers $s_i$ ($0 \leq s_i \leq n-1$) and $t_i$ ($0 \leq t_i \leq n-1$). Each denotes the $i$-th food should be transported from restaurant $s_i$ to $t_i$. You may assume $s_i \neq t_i$ for any $0 \leq i \leq q-1$, and $s_i \neq s_j$ or $t_i \neq t_j$ if $i \neq j$ for any $0 \leq i , j \leq q-1$.

Output

Print the minimum total cost of the foods transportation. If it is impossible to transport all foods to each destination, print -1.

Sample Input 1

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

Output for the Sample Input 1

6

Sample Input 2

5 3
4 5 6 7 8
0 1
0 3
4 2

Output for the Sample Input 2

32

Problem Statement

You are given an integer $N$, which is greater than $1$.

Consider the following functions:

• $f(a) = a^N \bmod N$
• $F_1(a) = f(a)$
• $F_{k+1}(a) = F_k(f(a))~~(k = 1,2,3,\ldots)$

Note that we use $\mathrm{mod}$ to represent the integer modulo operation. For a non-negative integer $x$ and a positive integer $y$, $x \bmod y$ is the remainder of $x$ divided by $y$.

Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than $N$. If no such $k$ exists, output $-1$.

Input

The input consists of a single line that contains an integer $N$ ($2 \le N \le 10^9$), whose meaning is described in the problem statement.

Output

Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than $N$, or $-1$ if no such $k$ exists.

Sample Input 1

3

Output for the Sample Input 1

1

Sample Input 2

4

Output for the Sample Input 2

-1

Sample Input 3

15

Output for the Sample Input 3

2

Problem Statement

There are $N$ points and $M$ segments on the $xy$-plane. Each segment connects two of these points and they don't intersect each other except at the endpoints. You are also given $Q$ points as queries. Your task is to determine for each query point whether you can make a polygon that encloses the query point using some of the given segments. Note that the polygon should not necessarily be convex.

Input

Each input is formatted as follows.

$N$ $M$ $Q$
$x_1$ $y_1$
...
$x_N$ $y_N$
$a_1$ $b_1$
...
$a_M$ $b_M$
$qx_1$ $qy_1$
...
$qx_Q$ $qy_Q$

The first line contains three integers $N$ ($2 \leq N \leq 100{,}000$), $M$ ($1 \leq M \leq 100{,}000$), and $Q$ ($1 \leq Q \leq 100{,}000$), which represent the number of points, the number of segments, and the number of queries, respectively. Each of the following $N$ lines contains two integers $x_i$ and $y_i$ ($-100{,}000 \leq x_i, y_i \leq 100{,}000$), the coordinates of the $i$-th point. The points are guaranteed to be distinct, that is, $(x_i, y_i) \neq (x_j, y_j)$ when $i \neq j$. Each of the following $M$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i \lt b_i \leq N$), which indicate that the $i$-th segment connects the $a_i$-th point and the $b_i$-th point. Assume that those segments do not intersect each other except at the endpoints. Each of the following $Q$ lines contains two integers $qx_i$ and $qy_i$ ($-100{,}000 \leq qx_i, qy_i \leq 100{,}000$), the coordinates of the $i$-th query point.

You can assume that, for any pair of query point and segment, the distance between them is at least $10^{-4}$.

Output

The output should contain $Q$ lines. Print "Yes" on the $i$-th line if there is a polygon that contains the $i$-th query point. Otherwise print "No" on the $i$-th line.

Sample Input 1

4 5 3
-10 -10
10 -10
10 10
-10 10
1 2
1 3
1 4
2 3
3 4
-20 0
1 0
20 0

Output for the Sample Input 1

No
Yes
No

Sample Input 2

8 8 5
-20 -20
20 -20
20 20
-20 20
-10 -10
10 -10
10 10
-10 10
1 2
1 4
2 3
3 4
5 6
5 8
6 7
7 8
-25 0
-15 0
0 0
15 0
25 0

Output for the Sample Input 2

No
Yes
Yes
Yes
No

Sample Input 3

8 8 5
-20 -10
-10 -10
-10 10
-20 10
10 -10
20 -10
20 10
10 10
1 2
2 3
3 4
1 4
5 6
6 7
7 8
5 8
-30 0
-15 0
0 0
15 0
30 0

Output for the Sample Input 3

No
Yes
No
Yes
No

Problem Statement

Since members of Kitafuji High School Brass Band Club succeeded in convincing their stern coach of their playing skills, they will be able to participate in Moon Light Festival as a marching band. This festival is a prelude in terms of appealing their presence for the coming domestic contest. Hence, they want to attract a festival audience by their performance.

Although this festival restricts performance time up to $P$ minutes, each team can freely determine their performance course from a provided area. The provided area consists of $N$ checkpoints, numbered $1$ through $N$, and $M$ bidirectional roads connecting two checkpoints. Kitafuji Brass Band already has the information about each road: its length and the expected number of people on its roadside. Each team must start at the checkpoint $1$, and return back to the checkpoint $1$ in $P$ minutes. In order to show the performance ability of Kitafuji Brass Band to a festival audience, their stern coach would like to determine their performance course so that many people listen their march as long as possible.

The coach uses "impression degree" to determine their best course. If they play $m$ minutes on the road with length $d$ and the expected number $v$ of people, then the impression degree will be $m \times v / d$. The impression degree of a course is the sum of impression degree of their performance on the course. Marching bands must move at a constant speed during marching: $1$ unit length per $1$ minute. On the other hand, they can turn in the opposite direction at any time, any place including a point on a road. The impression degree is accumulated even if they pass the same interval two or more times.

Your task is to write a program to determine a course with the maximum impression degree in order to show the performance ability of Kitafuji Brass Band to an audience as much as possible.

Input

The input is formatted as follows.

$N$ $M$ $P$
$s_1$ $t_1$ $d_1$ $v_1$
$\ldots$
$s_M$ $t_M$ $d_M$ $v_M$

The first line contains three integers $N$, $M$, and $P$: the number of checkpoints $N$ ($2 \le N \le 200$), the number of roads $M$ ($N-1 \le M \le N(N-1)/2$), and the performance time $P$ ($1 \le P \le 1{,}000$). The following $M$ lines represent the information about roads. The $i$-th line of them contains four integers $s_i$, $t_i$, $d_i$, and $v_i$: the $i$-th road bidirectionally connects between checkpoints $s_i$ and $t_i$ ($1 \le s_i, t_i \le N$, $s_i \neq t_i$) with length $d_i$ ($1 \le d_i \le 1{,}000$) and the expected number $v_i$ ($1 \le v_i \le 1{,}000$) of people.

You can assume that any two checkpoints are directly or indirectly connected with one or more roads. You can also assume that there are no pair of roads having the same pair of endpoints.

Output

Output the maximum impression degree of a course for a $P$-minute performance. The absolute error should be less than $10^{-4}$.

Sample Input 1

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1

Output for the Sample Input 1

6

Sample Input 2

4 3 9
1 2 2 1
1 3 2 2
1 4 2 3

Output for the Sample Input 2

13.5

Sample Input 3

4 3 5
1 2 10 1
2 3 2 100
1 4 3 10

Output for the Sample Input 3

16.6666666667

Sample Input 4

3 3 10
1 2 3 1
1 3 4 5
2 3 2 10

Output for the Sample Input 4

22

Problem Statement

Taro likes a signle player game "Surface Area of Cubes".

In this game, he initially has an $A \times B \times C$ rectangular solid formed by $A \times B \times C$ unit cubes (which are all 1 by 1 by 1 cubes). The center of each unit cube is placed at 3-dimensional coordinates $(x,y,z)$ where $x,y,z$ are all integers $(0\leq x\leq A-1, 0\leq y\leq B-1, 0\leq z\leq C-1)$. Then, $N$ distinct unit cubes are removed from the rectangular solid by the game master. After the $N$ cubes are removed, he must precisely tell the total surface area of this object in order to win the game.

Note that the removing operation does not change the positions of the cubes which are not removed. Also, not only the cubes on the surface of the rectangular solid but also the cubes at the inside can be removed. Moreover, the object can be divided into multiple parts by the removal of the cubes. Notice that a player of this game also has to count up the surface areas which are not accessible from the outside.

Taro knows how many and which cubes were removed but this game is very difficult for him, so he wants to win this game by cheating! You are Taro's friend, and your job is to make a program to calculate the total surface area of the object on behalf of Taro when you are given the size of the rectangular solid and the coordinates of the removed cubes.

Input

The input is formatted as follows.

The first line of a test case contains four integers $A,B,C$, and $N (1\leq A,B,C\leq 10^8,0\leq N\leq \min \{1{,}000, A\times B\times C-1 \} ).$

Each of the next $N$ lines contains non-negative integers $x,y$, and $z$ which represent the coordinate of a removed cube. You may assume that these coordinates are distinct.

Output

Output the total surface area of the object from which the $N$ cubes were removed.

Sample Input 1

2 2 2 1
0 0 0

Output for the Sample Input 1

24

Sample Input 2

1 1 5 2
0 0 1
0 0 3

Output for the Sample Input 2

18

Sample Input 3

3 3 3 1
1 1 1

Output for the Sample Input 3

60

Problem Statement

Ciel is going to do woodworking. Ciel wants to make a cut in a wooden board using a laser cutter.

To make it simple, we assume that the board is a two-dimensional plane. There are several segments on the board along which Ciel wants to cut the board. Each segment has a direction and Ciel must cut those segments along their directions. Those segments are connected when you ignore the directions, that is, any two points on the segments are directly or indirectly connected by the segments.

While the laser cutter is powered on, it emits a laser which hits the board at a point and cuts the board along its trace. The laser initially points to $(x, y)$. Ciel can conduct the following two operations:

• Move the laser cutter with its power on and cut (a part of) a segment along its direction, or
• Move the laser cutter to any position with its power off. Ciel should not necessarily cut the whole segment at a time; she can start or stop cutting a segment at any point on the segments.

Ciel likes to be efficient, so she wants to know the shortest route such that the laser cutter cuts the whole parts of all the segments and then move back to the initial point. Your task is to write a program that calculates the minimum total moving distance of the laser cutter.

Input

The first line of the input contains an integer $n$ ($1 \leq n \leq 300$), the number of segments. The next line contains two integers $x$ and $y$ ($-1{,}000 \leq x, y \leq 1{,}000$), which is the initial position $(x, y)$ of the laser. The $i$-th of the following $n$ lines contains four integers $sx_i$, $sy_i$, $tx_i$ and $ty_i$ ($-1{,}000 \leq sx_i, sy_i, tx_i, ty_i \leq 1{,}000$), which indicate that they are the end points of the $i$-th segment, and that the laser cutter can cut the board in the direction from $(sx_i, sy_i)$ to $(tx_i, ty_i)$. The input satisfies the following conditions: For all $i$ ($1 \leq i \leq n$), $(sx_i, sy_i) \neq (tx_i, ty_i)$. The initial point $(x, y)$ lies on at least one of the given segments. For all distinct $i, j$ ($1 \leq i, j \leq n$), the $i$-th segment and the $j$-th segment share at most one point.

Output

Output a line containing the minimum total moving distance the laser cutter needs to travel to cut all the segments and move back to the initial point. The absolute error or the relative error should be less than $10^{-6}$.

Sample Input 1

3
0 1
0 0 0 1
0 1 0 2
0 2 0 3

Output for the Sample Input 1

6.0000000000000000

Sample Input 2

2
0 1
0 0 0 2
-1 1 1 1

Output for the Sample Input 2

6.8284271247461900

Sample Input 3

5
0 0
0 0 1 0
1 1 -1 1
-1 1 -1 -1
-1 -1 1 -1
1 -1 1 1

Output for the Sample Input 3

10.0000000000000000

Problem Statement

A famous Japanese idol group, JAG48, is planning the program for its next live performance. They have $N$ different songs, $\mathit{song}_1$, $\mathit{song}_2$, ..., and $\mathit{song}_N$. Each song has three integer parameters, $t_i$, $p_i$, and $f_i$: $t_i$ denotes the length of $\mathit{song}_i$, $p_i$ denotes the basic satisfaction points the audience will get when $\mathit{song}_i$ is performed, and $f_i$ denotes the feature value of $\mathit{song}_i$ that affects the audience's satisfaction. During the live performance, JAG48 can perform any number (but at least one) of the $N$ songs, unless the total length of the chosen songs exceeds the length of the live performance $T$. They can decide the order of the songs to perform, but they cannot perform the same song twice or more.

The goal of this live performance is to maximize the total satisfaction points that the audience will get. In addition to the basic satisfaction points of each song, the difference between the feature values of the two songs that are performed consecutively affects the total satisfaction points. If there is no difference, the audience will feel comfortable. However, the larger the difference will be, the more frustrated the audience will be.

Thus, the total satisfaction points will be calculated as follows:

• If $\mathit{song}_x$ is the first song of the live performance, the total satisfaction points just after $\mathit{song}_x$ is equal to $p_x$.
• If $\mathit{song}_x$ is the second or subsequent song of the live performance and is performed just after $\mathit{song}_y$, $p_x - (f_x - f_y)^2$ is added to the total satisfaction points, because the audience will get frustrated if $f_x$ and $f_y$ are different.

Help JAG48 find a program with the maximum total satisfaction points.

Input

The input is formatted as follows.

$N$ $T$
$t_1$ $p_1$ $f_1$
$\ldots$
$t_N$ $p_N$ $f_N$

The first line contains two integers $N$ and $T$: the number of the available songs $N$ ($1 \le N \le 4{,}000$), and the length of the live performance $T$ ($1 \le T \le 4{,}000$).

The following $N$ lines represent the parameters of the songs. The $i$-th line of them contains three integers, which are the parameters of $\mathit{song}_i$: the length $t_i$ ($1 \le t_i \le 4{,}000$), the basic satisfaction points $p_i$ ($1 \le p_i \le 10^8$), and the feature value $f_i$ ($1 \le f_i \le 10^4$).

You can assume that there is at least one song whose length is less than or equal to $T$.

Output

Output the maximum total satisfaction points that the audience can get during the live performance.

Sample Input 1

2 10
10 200 1
10 100 100

Output for the Sample Input 1

200

Sample Input 2

3 15
5 100 1
5 100 2
5 100 4

Output for the Sample Input 2

295

Sample Input 3

3 10
5 200 200
5 200 201
5 300 1

Output for the Sample Input 3

399

Sample Input 4

3 20
5 100 200
5 100 201
5 300 1

Output for the Sample Input 4

300

Sample Input 5

5 61
14 49 7
31 46 4
30 55 5
52 99 1
34 70 3

Output for the Sample Input 5

103

Problem Statement

JAG Company is a sweatshop (sweatshop is called "burakku kigyo" in Japanese), and you are the CEO for the company.

You are planning to determine $N$ employees' salary as low as possible (employees are numbered from $1$ to $N$). Each employee's salary amount must be a positive integer greater than zero. At that time, you should pay attention to the employees' contribution degree. If the employee $i$'s contribution degree $c_i$ is greater than the employee $j$'s contribution degree $c_j$, the employee $i$ must get higher salary than the employee $j$'s salary. If the condition is not satisfied, employees may complain about their salary amount.

However, it is not necessarily satisfied in all pairs of the employees, because each employee can only know his/her close employees' contribution degree and salary amount. Therefore, as long as the following two conditions are satisfied, employees do not complain to you about their salary amount.

• If the employees $i$ and $j$ are close to each other, $c_i < c_j \Leftrightarrow p_i < p_j$ must be satisfied, where $p_i$ is the employee $i$'s salary amount.
• If the employee $i$ is close to the employees $j$ and $k$, $c_j < c_k \Leftrightarrow p_j < p_k$ must be satisfied.

Write a program that computes the minimum sum of all employees' salary amount such that no employee complains about their salary.

Input

Each input is formatted as follows:

$N$
$c_1$ ... $c_N$
$M$
$a_1$ $b_1$
...
$a_M$ $b_M$

The first line contains an integer $N$ ($1 \le N \le100{,}000$), which indicates the number of employees. The second line contains $N$ integers $c_i$ ($1 \leq c_i \leq 100{,}000$) representing the contribution degree of employee $i$.

The third line contains an integer $M$ ($0 \leq M \leq 200{,}000$), which specifies the number of relationships. Each of the following $M$ lines contains two integers $a_i$ and $b_i$ ($a_i \neq b_i$, $1 \leq a_i, b_i \leq N$). It represents that the employees $a_i$ and $b_i$ are close to each other. There is no more than one relationship between each pair of the employees.

Output

Print the minimum sum of all employees' salary amounts in a line.

Sample Input 1

3
1 3 3
2
1 2
1 3

Output for the Sample Input 1

5

Sample Input 2

3
1 2 3
2
1 2
1 3

Output for the Sample Input 2

6

Sample Input 3

4
1 1 2 2
2
1 2
3 4

Output for the Sample Input 3

4

Sample Input 4

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

Output for the Sample Input 4

10

Sample Input 5

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

Output for the Sample Input 5

13