A - Bubbler

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 9 点

問題文

レストランに来た高橋君は A 円のランチと B 円のドリンクバーを注文しようとしています。
高橋君は C 円引きのドリンクバー割引券を持っており、割引券を利用すると合計 A + B － C 円で注文することができます。
一方、ランチとドリンクバーのセットメニューを D 円で注文することもできますが、割引券を適用することはできません。
高橋君がランチとドリンクバーの両方を注文するのに必要な最小の金額を出力してください。

制約

  • 1 \leq A \leq 1000
  • 1 \leq C \lt B \leq 1000
  • 1 \leq D \leq 1000
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

A B C D

出力

高橋君がランチとドリンクバーの両方を注文するのに必要な最小の金額を出力せよ。

入力例 1

600 200 100 750

出力例 1

700

割引券を使ったときの金額は 600 + 200 - 100 = 700 円、セットメニューを注文したときの金額は 750 円なので、高橋君は 700 円でランチとドリンクバーを注文することができます。

入力例 2

600 200 100 650

出力例 2

650

割引券を使ったときの金額は入出力例 1 と同様に 700 円ですが、セットメニューを注文したときの金額は 650 円なので、答えは 650 円になります。

入力例 3

800 200 100 900

出力例 3

900

Score : 9 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In a restaurant, Takahashi is about to order an A-yen lunch and a B-yen free refill service. (Yen is the Japanese currency.)
He has a coupon that gives C-yen discount on the free refill service, allowing him to order both for a total of A + B － C yen.
On the other hand, a set menu of the lunch and the free refill service is also available for D yen, but the coupon cannot be applied to this.
Print the minimum total amount of money needed for Takahashi to order both the lunch and the free refill service.

Constraints

  • 1 \leq A \leq 1000
  • 1 \leq C \lt B \leq 1000
  • 1 \leq D \leq 1000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the minimum total amount of money needed for Takahashi to order both the lunch and the free refill service, as an integer.

Sample Input 1

600 200 100 750

Sample Output 1

700

They cost 600 + 200 - 100 = 700 yen when he uses the coupon, and 750 yen when he orders the set menu, so he needs to pay 700 yen to order both.

Sample Input 2

600 200 100 650

Sample Output 2

650

Again they cost 700 yen when he uses the coupon, but the set menu costs 650 yen this time, so the answer is 650 yen.

Sample Input 3

800 200 100 900

Sample Output 3

900
B - intersection

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 8 点

問題文

それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A_1,A_2, \dots , A_N) と B=(B_1,B_2, \dots , B_M) が与えられます。

A と B の両方に含まれる要素を全て求め、値の小さい順に出力してください。

制約

  • 1 \leq N,M \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • i \neq j ならば A_i \neq A_j
  • i \neq j ならば B_i \neq B_j
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

出力

条件を満たす要素を、値の小さい順に空白区切りで全て出力せよ。

入力例 1

6 4
60 50 40 30 20 10
53 60 25 40

出力例 1

40 60

値の小さい順に出力する必要があるので、60 40 という提出は不正解になることに注意してください。

入力例 2

3 1
1 2 3
123

出力例 2



条件を満たす要素が存在しないこともあります。






Score : 8 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given a sequence of N positive integers and another of M positive integers: A=(A_1,A_2, \dots , A_N) and B=(B_1,B_2, \dots , B_M).


Find all common elements in A and B, and print them in ascending order.











Constraints
    

  • 1 \leq N,M \leq 1000
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • 1 \leq B_i \leq 10^9
    • 

  • A_i \neq A_j if i \neq j.
    • 

  • B_i \neq B_j if i \neq j.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M












Output
Print all the common elements in ascending order, with spaces in between.















Sample Input 1
6 4
60 50 40 30 20 10
53 60 25 40












Sample Output 1
40 60 



Be sure to print them in ascending order: printing 60 40 would be considered incorrect.













Sample Input 2
3 1
1 2 3
123












Sample Output 2


There may be no common elements.






			


			
		

	
		

		

			C - Number of Apperance
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 8 点







問題文
長さ N の整数列 A = (A_1,A_2,\ldots ,A_N) が与えられます。この整数列の中に整数 X は何回現れますか？











制約
    

  • 1 \leq N \leq 10^5
    • 

  • 1 \leq X \leq 10^9
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N X
A_1 A_2 \ldots A_N












出力
整数列 A の中に整数 X が現れる回数、すなわち A_i=X をみたす i の個数を出力せよ。















入力例 1
3 3
2 3 3












出力例 1
2



整数列 A の中に 3 という整数は 2 回現れます。













入力例 2
3 1
2 3 3












出力例 2
0














入力例 3
5 2
2 3 4 2 2












出力例 3
3







Score : 8 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given a sequence of N integers: A = (A_1,A_2,\ldots ,A_N). How many times does the integer X occur in this sequence?











Constraints
    

  • 1 \leq N \leq 10^5
    • 

  • 1 \leq X \leq 10^9
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N X
A_1 A_2 \ldots A_N












Output
Print the number of times the integer X occurs in the sequence A, that is, the number of indices i such that A_i=X.















Sample Input 1
3 3
2 3 3












Sample Output 1
2



In the sequence A, the integer 3 occurs twice.













Sample Input 2
3 1
2 3 3












Sample Output 2
0














Sample Input 3
5 2
2 3 4 2 2












Sample Output 3
3







			


			
		

	
		

		

			D - Divisor
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 7 点







問題文
正の整数 X, Y が与えられます。
X の正の約数の個数と Y の正の約数の個数を比較し、


    

  • X の正の約数の個数の方が多いなら X と出力し、
    • 

  • Y の正の約数の個数の方が多いなら Y と出力し、
    • 

  • 両者が等しいなら Z と出力してください。
    • 












制約
    

  • 1 \leq X, Y \leq 10^6
    • 

  • X, Y は整数
    • 
















入力
入力は以下の形式で標準入力から与えられる。


X Y












出力
答えを出力せよ。















入力例 1
4 6












出力例 1
Y



4 の正の約数は 1, 2, 4 の 3 つであり、6 の正の約数は 1, 2, 3, 6 の 4 つです。
6 の正の約数の方が 4 の正の約数より多いので、Y を出力します。













入力例 2
6 4












出力例 2
X














入力例 3
3 5












出力例 3
Z







Score : 7 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given positive integers X and Y.
Compare the number of positive divisors of X and that of Y.


    

  • If X has more positive divisors than Y does, print X.
    • 

  • If Y has more positive divisors than X does, print Y.
    • 

  • If X and Y have the same number of divisors, print Z.
    • 












Constraints
    

  • 1 \leq X, Y \leq 10^6
    • 

  • X and Y are integers.
    • 
















Input
Input is given from Standard Input in the following format:


X Y












Output
Print the answer.















Sample Input 1
4 6












Sample Output 1
Y



4 has three positive divisors: 1, 2, and 4, while 6 has four positive divisors: 1, 2, 3, and 6.
Since 6 has more positive divisors than 4 does, you should print Y.













Sample Input 2
6 4












Sample Output 2
X














Sample Input 3
3 5












Sample Output 3
Z







			


			
		

	
		

		

			E - Colorful T-Shirts
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 7 点







問題文
N 枚の T シャツが売られています。各 T シャツの色は 1 以上 10^9 以下の整数で表され、i 枚目の T シャツの色は c_i で価格は p_i 円です。


K 種類の色の T シャツを集めるには最小で何円必要ですか？


ただし、K 種類の色の T シャツを集めることが不可能な場合は -1 を出力してください。











制約
    

  • 1 \leq N \leq 10^5
    • 

  • 1 \leq K \leq N+1
    • 

  • 1 \leq c_i,p_i \leq 10^9
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N K
c_1 c_2 \ldots c_N
p_1 p_2 \ldots p_N












出力
答えを（単位を除いて）出力せよ。















入力例 1
3 2
2 1 2
3 4 5












出力例 1
7



1 枚目と 2 枚目の T シャツを買うのが最適です。













入力例 2
3 3
2 1 2
3 4 5












出力例 2
-1














入力例 3
4 2
4 10 2 4
1 5 3 2












出力例 3
4







Score : 7 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
A shop sells N T-shirts. The color of each T-shirt is represented as an integer between 1 and 10^9 (inclusive). The i-th T-shirt has a color of c_i and a price of p_i yen (Japanese currency).


What is the minimum amount of money needed to get T-shirts of K different colors?


If it is impossible to get T-shirts of K different colors, print -1.











Constraints
    

  • 1 \leq N \leq 10^5
    • 

  • 1 \leq K \leq N+1
    • 

  • 1 \leq c_i,p_i \leq 10^9
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N K
c_1 c_2 \ldots c_N
p_1 p_2 \ldots p_N












Output
Print the answer (as a single integer).















Sample Input 1
3 2
2 1 2
3 4 5












Sample Output 1
7



The optimal choice is to buy the first and second T-shirts.













Sample Input 2
3 3
2 1 2
3 4 5












Sample Output 2
-1














Sample Input 3
4 2
4 10 2 4
1 5 3 2












Sample Output 3
4






			


			
		

	
		

		

			F - Incomplete Permutation
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 7 点







問題文
長さ N の 0 および 1 のみからなる文字列 S が与えられるので、以下の条件を全て満たす長さ N の数列 P=(P_1,P_2,\dots,P_N) をひとつ求めて下さい。ただし、そのようなものが存在しない場合は -1 と出力してください。


    

  • 数列 P は (1,2,\dots,N) の順列である、すなわち P は (1,2,\dots,N) を並べ替えたものである。
    • 

  • 全ての 1 \le i \le N について、以下の条件を満たす。
      

    • S の i 文字目が 1 なら、 P_i=i である。
      • 

    • S の i 文字目が 0 なら、 P_i \neq i である。
      • 

    

    • 












制約
    

  • 1 \le N \le 10^5
    • 

  • S は 0 および 1 のみからなる。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N
S












出力
条件を満たす数列 P が存在しない場合、 -1 と出力せよ。

存在する場合、数列 P の各項を整数として空白区切りで出力せよ。















入力例 1
5
10101












出力例 1
1 4 3 2 5



S の 1,3,5 文字目は 1 なので、 P_1=1,P_3=3,P_5=5 である必要があります。

S の 2,4 文字目は 0 なので、 P_2 \neq 2, P_4 \neq 4 である必要があります。

この入力の場合、題意を満たす数列 P として考えられるものは、 (1,4,3,2,5) のみです。













入力例 2
4
1110












出力例 2
-1



条件を満たす数列 P が存在しない場合、 -1 と出力してください。













入力例 3
12
001110110010












出力例 3
12 6 3 4 5 1 7 8 2 9 11 10



他にも、以下のような出力も正答と扱われます。


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







Score : 7 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
Given a string S of length N consisting of 0 and 1, find a sequence of length N, P=(P_1, P_2, \dots, P_N), that satisfies all of the following conditions. If no such sequence exists, print -1.


    

  • P is a permutation of (1,2,\dots,N).
    • 

  • The following holds for every 1 \le i \le N.
      

    • P_i=i if the i-th character of S is 1;
      • 

    • P_i \neq i if the i-th character of S is 0.
      • 

    

    • 












Constraints
    

  • 1 \le N \le 10^5
    • 

  • S consists of 0 and 1.
    • 
















Input
Input is given from Standard Input in the following format:


N
S












Output
If there is no sequence P that satisfies the conditions, print -1.

If such a sequence P exists, print its elements as integers, with spaces in between.















Sample Input 1
5
10101












Sample Output 1
1 4 3 2 5



The first, third, and fifth characters of S are 1, so we must have P_1=1,P_3=3,P_5=5.

The second and fourth characters of S are 0, so we must have P_2 \neq 2, P_4 \neq 4.

In this case, the only sequence P that satisfies the requirements is (1,4,3,2,5).













Sample Input 2
4
1110












Sample Output 2
-1



If there is no sequence P that satisfies the conditions, print -1.













Sample Input 3
12
001110110010












Sample Output 3
12 6 3 4 5 1 7 8 2 9 11 10



There are also other valid outputs, such as:


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







			


			
		

	
		

		

			G - K-th element
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
数列が N 個あり、i 番目の数列は長さ A_i, 初項 B_i, 公差 C_i の等差数列です。

N 個の数列を全て連結して 1 つの数列にしたとき、小さい方から K 番目の要素を答えてください。











制約
    

  • 2 \leq N \leq 10^5
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • 1 \leq B_i \leq 10^9
    • 

  • 1 \leq C_i \leq 10^9
    • 

  • \displaystyle 1 \leq K \leq \sum_{i=1}^N A_i
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N K
A_1 B_1 C_1
\vdots
A_N B_N C_N












出力
連結した数列の小さい方から K 番目の要素を出力せよ。















入力例 1
2 4
3 2 2
2 3 4












出力例 1
6



1 番目の数列は (2, 4, 6) 、2 番目の数列は (3, 7) なので、この二つの数列を連結すると (2, 4, 6, 3, 7) になります。

よって 4 番目に小さい要素は 6 となります。













入力例 2
2 10
4 1000000000 1000000000
6 1000000000 1000000000












出力例 2
6000000000



答えが 32 bit 整数に収まらない可能性があることに注意してください。













入力例 3
5 10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9












出力例 3
16







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
We have N sequences of numbers. The i-th of them is an arithmetic progression of length A_i with the initial term B_i and the common difference C_i.

If all these N sequences are concatenated into one sequence, what is the K-th smallest element of that sequence?











Constraints
    

  • 2 \leq N \leq 10^5
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • 1 \leq B_i \leq 10^9
    • 

  • 1 \leq C_i \leq 10^9
    • 

  • \displaystyle 1 \leq K \leq \sum_{i=1}^N A_i
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N K
A_1 B_1 C_1
\vdots
A_N B_N C_N












Output
Print the K-th smallest element of the sequence after the concatenation.















Sample Input 1
2 4
3 2 2
2 3 4












Sample Output 1
6



The first sequence is (2, 4, 6), and the second sequence is (3, 7), so we have (2, 4, 6, 3, 7) after the concatenation.

Therefore, the fourth smallest element is 6.













Sample Input 2
2 10
4 1000000000 1000000000
6 1000000000 1000000000












Sample Output 2
6000000000



Note that the answer may not fit into a 32-bit integer.













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












Sample Output 3
16







			


			
		

	
		

		

			H - Shortest Path
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と 1 から N-1 の番号がついた N-1 本の道路があり、全ての都市同士は互いに行き来することができます。

道路 i は 都市 a_i と都市 b_i を双方向に結ぶ長さ c_i キロメートルの道路です。


正の整数 X が与えられるので、次の条件を満たす相異なる都市の組 (i,j) が存在するか判定して、存在する場合は Yes を、存在しない場合は No を出力してください。


    

  • 都市 i から都市 j へ道路を利用して最短距離で移動したときの経路の長さが X キロメートルになる。
    • 












制約
    

  • 2 \leq N \leq 3000
    • 

  • 1 \leq a_i \lt b_i \leq N
    • 

  • 全ての都市同士は互いに行き来できる。
    • 

  • 1 \leq c_i \lt 10^5
    • 

  • 1 \leq X \leq 10^9
    • 

  • 入力中の全ての値は整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N X
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}












出力
条件を満たす都市の組が存在する場合は Yes を、存在しない場合は No を出力せよ。















入力例 1
3 5
1 2 3
1 3 2












出力例 1
Yes



都市 2 から都市 3 への最短経路は 5 キロメートルで、これは条件を満たします。よって Yes を出力します。













入力例 2
3 4
1 2 3
1 3 2












出力例 2
No



最短経路の長さが 4 キロメートルであるような都市の組は存在しません。よって No を出力します。













入力例 3
10 15
3 8 3
5 9 3
6 7 1
7 8 1
2 8 5
2 4 5
4 9 3
1 4 5
1 10 2












出力例 3
Yes







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1, where it is possible to travel between every pair of cities.

Road i connects Cities a_i and b_i bidirectionally and has a length of c_i kilometers.


Given a positive integer X, determine whether there is a pair of different cities (i, j) satisfying the condition below. If it exists, print Yes; otherwise, print No.


    

  • The shortest path from City i to City j using roads has the length of X kilometers.
    • 












Constraints
    

  • 2 \leq N \leq 3000
    • 

  • 1 \leq a_i \lt b_i \leq N
    • 

  • It is possible to travel between every pair of cities.  
    • 

  • 1 \leq c_i \lt 10^5
    • 

  • 1 \leq X \leq 10^9
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N X
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}












Output
If there is a pair of cities (i, j) satisfying the condition, print Yes; otherwise, print No.















Sample Input 1
3 5
1 2 3
1 3 2












Sample Output 1
Yes



The shortest path from City 2 to City 3 has the length of 5 kilometers, meeting the requirement, so you should print Yes.













Sample Input 2
3 4
1 2 3
1 3 2












Sample Output 2
No



There is no pair of cities such that the shortest path between them has the length of 4 kilometers, so you should print No.













Sample Input 3
10 15
3 8 3
5 9 3
6 7 1
7 8 1
2 8 5
2 4 5
4 9 3
1 4 5
1 10 2












Sample Output 3
Yes







			


			
		

	
		

		

			I - /2 and *3
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
長さ N の正整数のみからなる数列 A=(A_1,A_2,\dots,A_N) が与えられます。

この数列に以下の操作を 0 回以上何度でも行ってよいとき、数列の項の最小値として達成可能な最大値を求めてください。


    

  • まず、数列の中から偶数である項を 1 つ選び、その項を 2 で割る。次に、数列の中から任意の項を 1 つ選び、その項を 3 倍する。
    • 












制約
    

  • 入力は全て整数
    • 

  • 1 \le N \le 10^5
    • 

  • 1 \le A_i \le 10^9
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N
A_1 A_2 \dots A_N












出力
答えを整数として出力せよ。















入力例 1
3
18 21 46












出力例 1
23



例えば、以下の操作を行うことで、項の最小値を 23 にすることができます。


    

  • はじめ、A=(18,21,46) である。
    • 

  • A_1 を 2 で割り、 A_1 を 3 倍する。この操作の後、数列は A=(27,21,46) となる。
    • 

  • A_3 を 2 で割り、 A_2 を 3 倍する。この操作の後、数列は A=(27,63,23) となる。
    • 














入力例 2
5
3 5 7 11 13












出力例 2
3



一度も操作が行えない場合もあります。













入力例 3
1
536870912












出力例 3
68630377364883



答えが 32 bit 符号付き整数型に収まらないこともあります。






Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).

It is allowed to do the operation below any number of times, possibly zero. Find the largest value that can be taken by the smallest element of the sequence.


    

  • First, choose one element of the sequence that is an even number, and divide it by 2. Next, choose any one element, and multiply it by 3.
    • 












Constraints
    

  • All values in input are integers.
    • 

  • 1 \le N \le 10^5
    • 

  • 1 \le A_i \le 10^9
    • 
















Input
Input is given from Standard Input in the following format:


N
A_1 A_2 \dots A_N












Output
Print the answer as an integer.















Sample Input 1
3
18 21 46












Sample Output 1
23



One way to make the smallest element 23 is as follows.


    

  • Initially, we have A=(18,21,46).
    • 

  • Divide A_1 by 2 and multiple A_1 by 3, making A=(27,21,46).
    • 

  • Divide A_3 by 2 and multiple A_2 by 3, making A=(27,63,23).
    • 














Sample Input 2
5
3 5 7 11 13












Sample Output 2
3



It may be impossible to do the operation at all.













Sample Input 3
1
536870912












Sample Output 3
68630377364883



The answer may not fit into a 32-bit integer type.






			


			
		

	
		

		

			J - Reverse Array
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
長さ 2N の数列 A = (1,2, \ldots ,2N) があります。Q 個のクエリを処理してください。i 番目のクエリでは、整数 t_i, k_i が与えられます。


    

  • t_i = 1 のとき : 数列 A の左から k_i 番目の要素の値を出力する。
    • 

  • t_i = 2 のとき : 数列 A の中央の 2k_i 個の要素の順序を反転させる。つまり、左から N-k_i+1 番目の要素から左から N+k_i 番目の要素までの順序を反転させる。
    • 












制約
    

  • 1 \leq N \leq 2 \times 10^5
    • 

  • 1 \leq Q \leq 2 \times 10^5
    • 

  • 1 \leq t_i \leq 2
    • 

  • t_i=1 なる i が 1 つ以上存在する。
    • 

  • t_i=1 ならば 1 \leq k_i \leq 2N
    • 

  • t_i=2 ならば 1 \leq k_i \leq N
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N Q
t_1 k_1
t_2 k_2
\vdots
t_Q k_Q













出力
t_i=1 をみたす i について、それぞれ数列 A の左から k_i 番目の要素の値を改行区切りで出力せよ。















入力例 1
3 2
2 2
1 4













出力例 1
3




はじめ数列 A は (1,2,3,4,5,6) です。


1 つ目のクエリでは、中央の 4 要素を反転させ、数列 A は (1,5,4,3,2,6) となります。


2 つ目のクエリでは、左から 4 番目の要素は 3 なので、3 と出力してください。













入力例 2
3 3
2 3
1 3
1 1













出力例 2
4
6















入力例 3
5 6
2 2
2 1
2 1
2 3
1 2
2 3













出力例 3
2







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
We have a sequence of length 2N: A = (1,2, \ldots ,2N). Process Q queries. In the i-th query, you are given integers t_i and k_i.


    

  • If t_i = 1: print the value of the k_i-th element of the sequence A from the left.
    • 

  • If t_i = 2: reverse the order of the 2k_i elements at the center of the sequence A. In other words, reverse the order of the (N-k_i+1)-th through (N+k_i)-th elements from the left.
    • 












Constraints
    

  • 1 \leq N \leq 2 \times 10^5
    • 

  • 1 \leq Q \leq 2 \times 10^5
    • 

  • 1 \leq t_i \leq 2
    • 

  • There is at least one index i such that t_i=1.
    • 

  • 1 \leq k_i \leq 2N if t_i=1.
    • 

  • 1 \leq k_i \leq N if t_i=2.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N Q
t_1 k_1
t_2 k_2
\vdots
t_Q k_Q













Output
For each i such that t_i=1, print the value of the k_i-th element of the sequence A from the left, in its own line.















Sample Input 1
3 2
2 2
1 4













Sample Output 1
3




Initially, the sequence A is (1,2,3,4,5,6).


In the first query, we reverse the middle four elements, making A = (1,5,4,3,2,6).


In the second query, the fourth element from the left is 3, so you should print 3.













Sample Input 2
3 3
2 3
1 3
1 1













Sample Output 2
4
6















Sample Input 3
5 6
2 2
2 1
2 1
2 3
1 2
2 3













Sample Output 3
2







			


			
		

	
		

		

			K - Happy Wedding!
			

			
Time Limit: 5 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
ニワトリのオスが P 羽、メスが Q 羽います。

オスには 1,2,\dots,P 、メスには 1,2,\dots,Q の番号がつけられています。

また、0 と 1 のみからなる P 行 Q 列の行列 S が与えられます。

S の上から i 行目、左から j 列目、すなわち、 S_{i,j} が 1 であるときオス i とメス j は仲が良く、 0 であるときオス i とメス j は仲が悪いです。  


このもとで、仲の良いニワトリのオスとメスのペアをいくつか(0 組でもよい)選んでつがいにすることを考えます。但し、同じニワトリを複数のつがいに含めることはできません。もちろん仲が悪いニワトリのオスとメスのペアをつがいにすることもできません。


つがいを組んだ後、各ニワトリの幸福度は以下のようになります。


    

  • オス i がいずれかのつがいに含まれるならそのオスの幸福度は A_i 、含まれないならそのオスの幸福度は B_i となる。  
    • 

  • メス i がいずれかのつがいに含まれるならそのメスの幸福度は C_i 、含まれないならそのメスの幸福度は D_i となる。
    • 



うまくつがいを作ることで、 P+Q 羽のニワトリの幸福度の総和として達成可能な最大値を求めてください。











制約
    

  • P,Q,A_i,B_i,C_i,D_i は全て整数
    • 

  • 1 \le P,Q \le 100
    • 

  • S は 0 と 1 のみからなる P 行 Q 列の行列である
    • 

  • 1 \le A_i,B_i,C_i,D_i \le 10^9
    • 
















入力
入力は以下の形式で標準入力から与えられる。


P Q
S_{1,1}S_{1,2} \dots S_{1,Q}
S_{2,1}S_{2,2} \dots S_{2,Q}
\vdots
S_{P,1}S_{P,2} \dots S_{P,Q}
A_1 B_1
A_2 B_2
\dots
A_P B_P
C_1 D_1
C_2 D_2
\dots
C_Q D_Q












出力
答えを整数として出力せよ。















入力例 1
4 4
0010
1111
0010
0010
7 4
6 1
4 9
5 3
1 1
2 8
9 4
6 5












出力例 1
49



たとえば、オス 1 とメス 3 、オス 2 とメス 4 をつがいにする時、幸福度の総和は 7+6+9+3+1+8+9+6=49 となり、これが最適です。













入力例 2
3 4
0000
0000
0000
1 2
3 4
5 6
7 8
9 10
11 12
13 14












出力例 2
56



1 組もつがいを作れない場合も、 1 組もつがいを作らないことが最適である場合もあります。













入力例 3
4 3
100
100
100
111
5 4
3 2
9 8
100 1
200 50
10 9
8 6












出力例 3
332







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
There are P roosters and Q hens.

The roosters are numbered 1,2,\dots,P, and the hens are numbered 1,2,\dots,Q.

Additionally, you are given a P-by-Q matrix S consisting of 0 and 1.

If the element at the i-th from the top and j-th column from the left of S, or S_{i,j}, is 1, Rooster i and Hen j are on good terms; if S_{i,j} is 0, they are on bad terms.


Consider choosing some number (possibly zero) of pairs of a rooster and a hen on good terms to form couples. It is not allowed to include the same chicken in multiple couples, and neither is it to pair up a rooster and a hen on bad terms.


After some couples are formed, each chicken will have the following happiness.


    

  • If Rooster i belongs to a couple, his happiness will be A_i; otherwise, his happiness will be B_i.
    • 

  • If Hen i belongs to a couple, her happiness will be C_i; otherwise, her happiness will be D_i.
    • 



Find the maximum possible total happiness of the P+Q chickens, achieved by forming optimal couples.











Constraints
    

  • P,Q,A_i,B_i,C_i,D_i are all integers.
    • 

  • 1 \le P,Q \le 100
    • 

  • S is a P-by-Q matrix consisting of 0 and 1.
    • 

  • 1 \le A_i,B_i,C_i,D_i \le 10^9
    • 
















Input
Input is given from Standard Input in the following format:


P Q
S_{1,1}S_{1,2} \dots S_{1,Q}
S_{2,1}S_{2,2} \dots S_{2,Q}
\vdots
S_{P,1}S_{P,2} \dots S_{P,Q}
A_1 B_1
A_2 B_2
\dots
A_P B_P
C_1 D_1
C_2 D_2
\dots
C_Q D_Q












Output
Print the answer as an integer.















Sample Input 1
4 4
0010
1111
0010
0010
7 4
6 1
4 9
5 3
1 1
2 8
9 4
6 5












Sample Output 1
49



If, for example, we pair Rooster 1 with Hen 3 and Rooster 2 with Hen 4, the total happiness will be 7+6+9+3+1+8+9+6=49, which is optimal.













Sample Input 2
3 4
0000
0000
0000
1 2
3 4
5 6
7 8
9 10
11 12
13 14












Sample Output 2
56



There may be no couple to form, and it may be optimal to form no couple.













Sample Input 3
4 3
100
100
100
111
5 4
3 2
9 8
100 1
200 50
10 9
8 6












Sample Output 3
332






			


			
		

	
		

		

			L - K-th Abs
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。

A の連続した空でない部分列 B に対して B のスコアを (B に含まれる要素の総和の絶対値 ) と定めます。

A の連続した空でない部分列は全部で \frac{N(N+1)}{2}  個ありますが、それらの部分列全てに対してスコアを計算したとき、小さい方から K 番目のスコアを求めてください。











制約
    

  • 2 \leq N \leq 3 \times 10^5
    • 

  • 1 \leq K \leq \frac{N(N+1)}{2}
    • 

  • -10^9 \leq A_i \leq 10^9
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N K
A_1 A_2 \dots A_N












出力
小さい方から K 番目のスコアを出力せよ。















入力例 1
2 2
2 -3












出力例 1
2



A の連続した空でない部分列およびスコアは次の通りです。


    

  • 列 (A_1) のスコアは | 2 | = 2 です。
    • 

  • 列 (A_2) のスコアは | -3 | = 3 です。
    • 

  • 列 (A_1, A_2) のスコアは | 2 + (-3) | = 1 です。
    • 














入力例 2
5 10
1000000000 1000000000 1000000000 1000000000 1000000000












出力例 2
3000000000



答えが 32 bit 整数に収まらない可能性があることに注意してください。













入力例 3
7 22
3 -1 4 -1 5 -9 2












出力例 3
5







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given a sequence of length N: A = (A_1, A_2, \dots, A_N).

For a non-empty contiguous subsequence B of A, let the score of B be the absolute value of the sum of elements in B.

Assume that we have computed the scores of all \frac{N(N+1)}{2} non-empty contiguous subsequences of A. Find the K-th smallest of these scores.











Constraints
    

  • 2 \leq N \leq 3 \times 10^5
    • 

  • 1 \leq K \leq \frac{N(N+1)}{2}
    • 

  • -10^9 \leq A_i \leq 10^9
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N K
A_1 A_2 \dots A_N












Output
Print the K-th smallest of these scores.















Sample Input 1
2 2
2 -3












Sample Output 1
2



The non-empty contiguous subsequences of A and their scores are as follows.


    

  • The sequence (A_1) has a score of | 2 | = 2.
    • 

  • The sequence (A_2) has a score of | -3 | = 3.
    • 

  • The sequence (A_1, A_2) has a score of | 2 + (-3) | = 1.
    • 














Sample Input 2
5 10
1000000000 1000000000 1000000000 1000000000 1000000000












Sample Output 2
3000000000



Note that the answer may not fit into a 32-bit integer.













Sample Input 3
7 22
3 -1 4 -1 5 -9 2












Sample Output 3
5







			


			
		

	
		

		

			M - Balance
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				
    
        
配点 : 6 点


        

            

                
注意

                
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
                    試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

            

        


        

            

                
問題文

                
N 頂点 M 辺の単純連結無向グラフ G が与えられます。

                    頂点には 1,\ldots,N の番号が、辺には 1,\ldots,M の番号がついており、辺 i は頂点
                    A_i と B_i を結んでいます。

                
辺 i には整数 C_i が書かれています。あなたは次の条件を満たすように、各頂点に 0 以上の整数を書こうとしています。

                
条件：全ての辺 i について、頂点 A_i に書かれた数と頂点 B_i に書かれた数の和が C_i に等しい
                

                
そのようなことが可能であれば一例を、不可能であればそのことを報告してください。

            

        


        

            

                
制約

                
    
                    
  • 2 \leq N \leq 10^5
    • 
                    
  • N-1 \leq M \leq 10^5
    • 
                    
  • 1 \leq A_i < B_i \leq N
    • 
                    
  • (A_i,B_i) は相異なる
    • 
                    
  • 0 \leq C_i \leq 10^9
    • 
                    
  • 与えられるグラフは連結
    • 
                    
  • 入力は全て整数
    • 
                

            

        


        

        

            

                

                    
入力

                    
入力は以下の形式で標準入力から与えられる。

                    
N M
A_1 B_1 C_1
\vdots
A_M B_M C_M


                

            


            

                

                    
出力

                    
条件を満たすような数の書き込み方が存在しなければ -1 と出力せよ。

                        存在するならば、頂点 i に書き込む数を i 行目に出力し、全部で N 行出力せよ。

                

            

        


        

        

            

                
入力例 1

                
3 2
1 2 2
2 3 1


            

        


        

            

                
出力例 1

                
1
1
0


                
頂点 1 に 1、頂点 2 に 1、頂点 3 に 0
                    を書くと、条件を満たすことが確かめられます。

                
他にも、頂点 1 に 2、頂点 2 に 0、頂点 3 に 1
                    を書いた場合も条件を満たします。

            

        


        

        

            

                
入力例 2

                
3 3
1 2 0
2 3 0
1 3 2


            

        


        

            

                
出力例 2

                
-1


                
頂点に書き込む数は 0 以上の整数でなければならないことに注意してください。

            

        

    
    
        
Score : 6 points


        

            

                
Warning

                
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation,
                    compensation may be demanded. After the examination, you can reveal your total score and grade to
                    others, but nothing more (for example, which problems you solved).

            

        


        

            

                
Problem Statement

                
You are given a simple connected undirected graph G with N vertices and
                    M edges.

                    The vertices are numbered 1, \ldots, N, and the edges are numbered 1, \ldots,
                        M. Edge i connects Vertices A_i and B_i.

                
Edge i has an integer C_i written on it. You are about to write an integer not
                    less than 0 on each vertex so that the following condition is satisfied.

                
Condition: For every edge i, the sum of the numbers written on Vertices A_i and
                    B_i equals C_i.

                
If this is possible, show one way to do it; if it is impossible, report that fact.

            

        


        

            

                
Constraints

                
    
                    
  • 2 \leq N \leq 10^5
    • 
                    
  • N-1 \leq M \leq 10^5
    • 
                    
  • 1 \leq A_i < B_i \leq N
    • 
                    
  • The pairs (A_i, B_i) are distinct.
    • 
                    
  • 0 \leq C_i \leq 10^9
    • 
                    
  • The given graph is connected.
    • 
                    
  • All values in input are integers.
    • 
                

            

        


        

        

            

                

                    
Input

                    
Input is given from Standard Input in the following format:

                    
N M
A_1 B_1 C_1
\vdots
A_M B_M C_M


                

            


            

                

                    
Output

                    
If there is no way to write numbers to satisfy the condition, print -1.

                        Otherwise, print the number to write on Vertex i in the i-th line, for a
                        total of N lines.

                

            

        


        

        

            

                
Sample Input 1

                
3 2
1 2 2
2 3 1


            

        


        

            

                
Sample Output 1

                
1
1
0


                
It can be verified that writing 1 on Vertex 1, 1 on Vertex
                    2, and 0 on Vertex 3 satisfies the condition.

                
Another way to satisfy the condition is to write 2 on Vertex 1, 0 on
                    Vertex 2, and 1 on Vertex 3.

            

        


        

        

            

                
Sample Input 2

                
3 3
1 2 0
2 3 0
1 3 2


            

        


        

            

                
Sample Output 2

                
-1


                
Note that the numbers to write on the vertices must be integers not less than 0.

            

        

    

			


			
		

	
		

		

			N - Zigzag Sequences
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
以下の 2 つの条件のうち、いずれかを満たす数列 B を「ジグザグな数列」と定義します。ここで、|B| は B の要素数を表します。


    

  • 長さが 2 以上であり、かつ、全ての i\ (1 \leq i \lt |B|) について以下が成り立つ。
      

    • i が奇数なら B_i \lt B_{i+1}
      • 

    • i が偶数なら B_i \gt B_{i+1} 
      • 

    

    • 

  • 長さが 2 以上であり、かつ、全ての i\ (1 \leq i \lt |B|) について以下が成り立つ。
      

    • i が奇数なら B_i \gt B_{i+1}
      • 

    • i が偶数なら B_i \lt B_{i+1} 
      • 

    

    • 



長さ N の数列 A が与えられます。A の空でない（連続するとは限らない）部分列は 2^N-1 個ありますが、そのうちジグザグな数列はいくつありますか？

個数を (10^9+7) で割った余りを出力してください。











制約
    

  • 2 \leq N \leq 2 \times 10^5
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N
A_1 A_2 \ldots A_N












出力
A の空でない部分列のうち、ジグザグな数列であるようなものの個数を (10^9+7) で割った余りを出力せよ。















入力例 1
3
1 3 2












出力例 1
4



A の空でない部分列は以下の 7 つです。そのうちジグザグな数列であるようなものは、星印で示された 4 つです。


    

  • (1)
    • 

  • (3)
    • 

  • (2)
    • 

  • (1,3) \cdots ☆
    • 

  • (1,2) \cdots ☆
    • 

  • (3,2) \cdots ☆
    • 

  • (1,3,2) \cdots ☆
    • 














入力例 2
3
1 3 3












出力例 2
2



2 つの部分列は列として同じであっても、取り出す位置が異なる場合は区別されることに注意してください。

このケースにおいて、A の部分列であってかつジグザグな数列であるようなものは (1,3) と (1,3) の 2 つです。













入力例 3
4
2 2 2 2












出力例 3
0



答えは 0 になることもあります。













入力例 4
6
83 65 79 54 88 69












出力例 4
44







Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
A sequence of numbers, B, is called zigzag when it satisfies one of the following two conditions, where |B| denotes the number of elements in B.


    

  • B has a length of at least 2, and the following holds for every i i\ (1 \leq i \lt |B|).
      

    • B_i \lt B_{i+1} if i is odd;
      • 

    • B_i \gt B_{i+1} if i is even.
      • 

    

    • 

  • B has a length of at least 2, and the following holds for every i i\ (1 \leq i \lt |B|).
      

    • B_i \gt B_{i+1} if i is odd;
      • 

    • B_i \lt B_{i+1} if i is even.
      • 

    

    • 



You are given a sequence A of length N. Among the 2^N-1 non-empty (not necessarily contiguous) subsequences of A, how many are zigzag?

Print the count modulo (10^9+7).











Constraints
    

  • 2 \leq N \leq 2 \times 10^5
    • 

  • 1 \leq A_i \leq 10^9
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N
A_1 A_2 \ldots A_N












Output
Print the number of zigzag sequences among the non-empty subsequences of A, modulo (10^9+7).















Sample Input 1
3
1 3 2












Sample Output 1
4



A has seven non-empty subsequences shown below. Among them, the four sequences marked with stars are zigzag.


    

  • (1)
    • 

  • (3)
    • 

  • (2)
    • 

  • (1,3) \cdots ☆
    • 

  • (1,2) \cdots ☆
    • 

  • (3,2) \cdots ☆
    • 

  • (1,3,2) \cdots ☆
    • 














Sample Input 2
3
1 3 3












Sample Output 2
2



Note that two subsequences are distinguished if they originate from different positions, even if these sequences are the same in themselves.

In this case, the two subsequences of A that are zigzag are (1,3) and (1,3).













Sample Input 3
4
2 2 2 2












Sample Output 3
0



The answer may be 0.













Sample Input 4
6
83 65 79 54 88 69












Sample Output 4
44







			


			
		

	
		

		

			O - Red Blue Tournament
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 6 点







注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。











問題文
(1,\ldots, 2^N) の順列 (P_1, P_2, \ldots ,P_{2^N}) が与えられます。
選手 1 から選手 2^N までの 2^N 人がトーナメント形式で戦う事を考えます。トーナメントは N ラウンドからなり、次のように行われます。


    

  • 第 1 ラウンドは 2^{N-1} 試合からなる。第 i \, (1 \leq i \leq 2^{N - 1}) 試合では選手 P_{2i-1} と選手 P_{2i} が戦う。
    • 

  • その後、k = 2, \dots, N の順に、第 k ラウンドが以下のように行われる。
      

    • 第 k ラウンドは 2^{N - k} 試合からなり、第 i \, (1 \leq i \leq 2^{N - k}) 試合では、第 k-1 ラウンドの第 2i - 1 試合における勝者と第 2i 試合における勝者が戦う。
      • 

    

    • 



各選手は、トーナメントの開始前に赤か青のいずれかの色を割り当てられます。全ての選手に同じ色が割り当てられることもありえます。


いま、トーナメントの結果について以下の事が分かっています。


    

  • 各試合において、対戦者に割り当てられた色が等しいならば、選手番号の小さい選手が勝利した。
    • 

  • 各試合において、対戦者に割り当てられた色が異なるならば、選手番号の大きい選手が勝利した。
    • 

  • 1\leq i\leq M について、いずれかの試合で選手 W_i と選手 L_i が戦い、選手 W_i が勝利した。
    • 



各選手に色を割り当てる方法であって、上の条件をすべてみたすものの数を 998244353 で割った余りを出力してください。ただし、情報が間違っており、条件をみたす色の割り当て方が 0 通りである可能性もあることに注意してください。











制約
    

  • 1 \leq N \leq 17
    • 

  • 1 \leq M < 2^N
    • 

  • 1 \leq P_i \leq 2^N
    • 

  • P_i は全て相異なる。
    • 

  • 1 \leq W_i, L_i \leq 2^N
    • 

  • W_i\neq L_i
    • 

  • (W_i,L_i) は全て相異なる。
    • 

  • 入力は全て整数である。
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N M
P_1 \ldots P_{2^N}
W_1 L_1
\vdots
W_M L_M












出力
条件をみたす色の割り当て方を 998244353 で割った余りを出力せよ。















入力例 1
1 1
2 1
1 2












出力例 1
2



トーナメントは 1 試合のみからなります。
選手 1 と選手 2 が対戦して選手 1 が勝利していることから 2 人に割り当てられた色は等しかった事が分かります。よって 2 人に割り当てられた色としてあり得るのは（赤, 赤）と（青, 青）の 2 通りあります。













入力例 2
2 2
1 2 3 4
2 3
1 2












出力例 2
0



選手 2 と選手 3 が対戦するのは第 2 ラウンドの第 1 試合しかありえないので、選手 2 は第 1 ラウンドで勝利している必要があります。

一方で、選手 1 と選手 2 が対戦するのは第 1 ラウンドの第 1 試合しかありえませんが、そこでは選手 1 が勝利したことが分かっています。

よって、このようなことはあり得ず、 条件をみたす割り当て方は 0 通りであることが分かります。






Score : 6 points







Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).











Problem Statement
You are given a permutation (P_1, P_2, \ldots ,P_{2^N}) of (1,\ldots, 2^N).
Consider a knockout tournament with 2^N players with ID numbers from 1 through 2^N. The tournament consists of N rounds that go as follows.


    

  • The first round consists of 2^{N-1} games. The i-th game (1 \leq i \leq 2^{N - 1}) is between Player P_{2i-1} and Player P_{2i}.
    • 

  • Then, for each k = 2, \dots, N in this order, the k-th round takes place as follows.
      

    • The k-th round consists of 2^{N - k} games. The i-th game (1 \leq i \leq 2^{N - k}) is between the winners of the (2i - 1)-th and 2i-th games in the (k-1)-th round.
      • 

    

    • 



Before the start of the tournament, each player is assigned a color which is red or blue. All players may be assigned the same color.


Here, the following information is known about the results of the tournament.


    

  • In each game, if the two players were assigned the same color, the player with the smaller ID number won.
    • 

  • In each game, if the two players were assigned different colors, the player with the larger ID number won.
    • 

  • For each 1\leq i\leq M, Player W_i and Player L_i fought in some game, and Player W_i won.
    • 



Find the number of ways to assign colors to the players that satisfy all of the conditions above, modulo 998244353. Beware that the information may be wrong, and there may be zero ways to assign colors that satisfy the conditions. 











Constraints
    

  • 1 \leq N \leq 17
    • 

  • 1 \leq M < 2^N
    • 

  • 1 \leq P_i \leq 2^N
    • 

  • All P_i are distinct.
    • 

  • 1 \leq W_i, L_i \leq 2^N
    • 

  • W_i\neq L_i
    • 

  • All pairs (W_i,L_i) are distinct.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


N M
P_1 \ldots P_{2^N}
W_1 L_1
\vdots
W_M L_M












Output
Print the number of ways to assign colors that satisfy the conditions, modulo 998244353.















Sample Input 1
1 1
2 1
1 2












Sample Output 1
2



The tournament consists of one game.
From the fact that Players 1 and 2 fought and Player 1 won, we learn that they were assigned the same color. Thus, there are two ways in which the players may have been assigned colors: (red, red) and (blue, blue).













Sample Input 2
2 2
1 2 3 4
2 3
1 2












Sample Output 2
0



The game between Players 2 and 3 could only be the first game in the second round, so Player 2 must have won in the first round.

On the other hand, the game between Players 1 and 2 could only be the first game in the first round, but the information says Player 1 won there.

Therefore, we conclude that the information is contradictory, and there are zero assignments of colors that are consistent with it.