問題文

N 頂点 M 本の無向辺からなる単純連結無向グラフが与えられます。 頂点に 1 から N の番号が、辺には 1 から M の番号がついています。 それぞれの頂点には色が塗られており、頂点 i は s_i が B ならば青で、R ならば赤で塗られています。

辺 i は頂点 a_i と b_i を双方向につなぐ辺です。

太郎君と次郎君がこのグラフを使ってゲームをすることにしました。

グラフ上のどこかの頂点に 1 つの駒が置かれています。 太郎君と次郎君は以下の操作を交互に行います。太郎君が最初に操作を行います。

• 操作：駒が置かれている頂点に隣接する頂点を 1 つ選び、選んだ頂点に駒を移動させる

操作を K 回行ったのち、駒が置かれている頂点の色が青ならば太郎君の、そうでなければ次郎君の勝利です。

はじめに駒が置かれている位置は N 通りありえます。 それぞれの場合について、2 人が最適に行動したときの勝者がどちらかを判定してください。

制約

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq 10^{18}
• |s| = N
• s_i は B あるいは R
• 1 \leq a_i,b_i \leq N
• 与えられるグラフは単純かつ連結

入力例1

2 1 3
BR
1 2

出力例1

Second
First

• 駒は 1 \rightarrow 2, 2 \rightarrow 1 のいずれかの移動を繰り返します。
• 駒が頂点 1 に置かれていたならば 3 回の操作後には頂点 2 に置かれているため次郎君が勝者となります。
• 駒が頂点 2 に置かれていたならば 3 回の操作後には頂点 1 に置かれているため太郎君が勝者となります。

入力例2

2 1 1000000000000000000
BR
1 2

出力例2

First
Second

入力例3

5 7 9
BRRBR
3 1
5 2
4 2
2 1
5 4
5 1
3 2

出力例3

Second
First
First
Second
First

問題文

長さ N の数列 a が与えられます。i 番目の要素は a_i です。

ニワンゴくんは a に対し、以下の操作を 0 回以上行うことができます。

• 操作：1 < i < N を満たす整数 i を選び、a_{i-1} を a_{i-1} \ {\rm{XOR}} \ a_{i} に、a_{i+1} を a_{i+1} \ {\rm{XOR}} \ a_{i} にそれぞれ置き換える。ここで {\rm{XOR}} はビットごとの排他的論理和の記号を表す。

0 回以上操作を行ったあとの a としてありうる数列のうち、辞書順最小のものを求めてください。

制約

• 1 \leq N \leq 10^5
• 0 \leq a_i \leq 10^{9}
• 与えられる入力は全て整数

入力例1

3
2 3 1

出力例1

1 3 2

• 1 回の操作により、(2,3,1) \rightarrow (2 \ \rm{XOR} \ 3, 3, 1 \ \rm{XOR} \ 3) = (1,3,2) と変化させることができます。

入力例2

5
1 1 3 2 1

出力例2

0 1 0 2 3

入力例3

15
454149310 980904516 263802120 650414794 570152508 496610001 940998475 895836185 33049807 966544922 733719158 536712208 292230877 949871052 342421559

出力例3

23988306 158687594 74711974 280079291 131007899 572247609 33049807 210457501 22094817 292230877 86347283 143004158 53812512 67781078 644469472

問題文

1 から N までの番号がついた N 頂点の無向グラフが与えられます。 はじめ、このグラフに辺はありません。

各頂点には半開区間が割り当てられており、頂点 i には [l_i, r_i) が割り当てられています。

ニワンゴくんは以下のルールで辺を追加しました。

• 2 つの頂点 i, j に割り当てられた 2 つの区間が 共通部分を持つ ならば頂点 i, j をつなぐ辺を追加する
• 追加される辺の長さは 2 つの区間の共通部分の長さである

このグラフの最小全域木に含まれる辺の長さの総和を求めてください。最小全域木が存在しないならば代わりに -1 を出力してください。

制約

• 1 \leq N \leq 10^5
• 1 \leq l_i < r_i \leq 10^9

入力例1

3
1 4
2 6
3 4

作られるグラフは以下の図の通りです。

Sample input 1

出力例1

2

入力例2

2
1 1000
1000 2000

出力例2

-1

入力例3

7
121 951
420 492
197 607
167 925
438 717
200 986
104 483

出力例3

387

入力例4

14
319 1000
411 456
115 626
380 764
517 757
679 764
526 801
967 990
475 604
249 416
199 406
557 954
355 991
505 539

出力例4

409

問題文

ドワンゴ社員のニワンゴ君は、括弧の対応が取れた文字列が大好きです。今日は、たくさんの括弧を並び替えて遊ぶことにしました。

ニワンゴくんは、( と ) のみからなる長さ N の文字列 S を持っています。S には ( と ) が同じ数だけ含まれます。

以下を満たす数列 p をいい数列と呼びます。

• (1, 2, 3, ..., N) を並び替えて得られる
• t_i = s_{p_i} なる文字列 t はバランスの取れた括弧列となる

いい数列であるような全ての数列について転倒数を計算し、その和を 10^{9}+7 で割った余りを出力してください。

ここで数列 p の転倒数は、p_i > p_j を満たすペア (i, j) (i < j) の個数として定義されます。また、「バランスの取れた括弧列」は以下のように定義されます。

1. 空文字列はバランスの取れた括弧列である
2. バランスの取れた括弧列を r とする。 (, r, ) をこの順に連結して得られる文字列はバランスの取れた括弧列である
3. 2 つのバランスの取れた括弧列をこの順に連結したものはバランスの取れた括弧列である
4. 上記の規則によって生成される文字列のみがバランスの取れた括弧列である

制約

• 2 \leq N \leq 5 \times 10^5
• S は ( と ) のみからなる
• S は ( と ) を同じ数含む
• |S| = N

入力例1

2
)(

出力例1

1

p としてありえる数列は (1, 2), (2, 1) の 2 通りあり、それぞれに対する文字列 t は )( と () です。いい数列は (2, 1) だけであり、この転倒数は 1 です。

入力例2

6
(())()

出力例2

1060

入力例3

16
)())()((((()))()

出力例3

58589334

• 答えを 10^{9}+7 で割った余りを求めるのを忘れずに