MoBrook | 溪月阁

参加了Codeforces Round #647 (Div. 2)，2.5小时还是只A了两道题，50分钟完成A、B两题，第三题通过列举找到规律，不过代码不对，高中数学不过关的锅，遇到一些知识漏洞，记录一下。

A. Johnny and Ancient Computer

》英文原题《

有一台计算机输入一个x只能进行不限次数的如下6种操作：
x乘2
x乘4
x乘8
if(!x%2)x/2
if(!x%4)x/4
if(!x%8)x/8
然后输出计算结果。

举个例子：
如果输入6，经过一次操作他可以返回12,24,48,3但是没办法/4或者/8 。

现在希望将a通过计算机操作输出b
如果可以，就输出操作次数的最小值；
如果不行就输出-1。

Input

第一行是一个int t (1≤t≤1000) — 输入test的数量，接着是t组test。

每个test包含2个int a, b (1≤a,b≤10₁₈) — 输入的数 目标的数。

Output

输出t个test的结果
将a通过计算机操作输出b
如果可以，就输出操作次数的最小值；
如果不行就输出-1。

Example

input

10
10 5
11 44
17 21
1 1
96 3
2 128
1001 1100611139403776
1000000000000000000 1000000000000000000
7 1
10 8

output

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

Note

第1组案例的情况:
10/2=5
结果：1

第2组案例的情况:
44/4=11
结果：1

第3组案例的情况:
17=>x21
结果：-1

第4组案例的情况:
0=0
结果：0

第5组案例的情况:
96/8=12
12/4=3
结果：2

---

B. Johnny and His Hobbies

》英文原题《

这里有一个数组 S ，现在需要找到一个 k 然后对数组 S 的每个数字进行如下操作 s⊕k (⊕ 表示按位异或)。

帮助我们找到一个 k ，使得数组 S 在经过操作之后仍然和原来一样（在这个数组中顺序不重要，即{1,2,3}和{2,1,3}是一样的）。

总而言之，需要你帮我们找到一个正整数 k 使得 {s⊕k|s∈S}=S ；如果找不到这样的数，那就返回-1。

举亿个例子：
如果 S={1,3,4} 并且 k=2, 操作结束后数组等于 {3,1,6}。
如果 S={0,1,2,3} 并且 k=1,, 操作结束后数组与原来一样。

Input

第一行是一个int t (1≤t≤1024) — 输入test的数量，接着是t组test。

每个test包含2行
第1行包含1个int n (1≤t≤1024)
第2行包含n个int s₁, s₂,...,s_n(0≤s_i<1024) — 数组 S 的元素。

保证每个test数据的 n 之和不大于1024

Output

输出t个test的结果
如果k存在，则输出k的最小值；
否则输出 -1 。

Example

input

6
4
1 0 2 3
6
10 7 14 8 3 12
2
0 2
3
1 2 3
6
1 4 6 10 11 12
2
0 1023

output

1
4
2
-1
-1
1023

Note

第1组案例的情况:
输入数组 1 0 2 3
二进制数 01 00 10 11
操作结果 00 01 11 10
结果数组 0 1 3 2
结果：1

---

C. Johnny and Another Rating Drop

》英文原题《

现有n+1位参赛者，序号为0,1,...,n。将数字转化成二进制之后与上一个序号不同的位数就是两个序号的差距，现需要你求出0到n号选手序号差距的总和。

举一个例子：
5和14两个数的差距
5=0101₂，14=1110₂
结果：3

Input

第一行是一个int t (1≤t≤10000) — 输入test的数量，接着是t组test。

每个test包含1个int n (1≤t≤10₁₈)

Output

输出t个test的结果
每个包含1个数 — 0到n号选手序号差距的总和。

Example

input

5
5
7
11
1
2000000000000

output

8
11
19
1
3999999999987

Note

第1组案例的情况:
5
000
001
010
011
100
101
结果：1+2+1+3+1=8

---

D. Johnny and Contribution

》英文原题《

Today Johnny wants to increase his contribution. His plan assumes writing n blogs. One blog covers one topic, but one topic can be covered by many blogs. Moreover, some blogs have references to each other. Each pair of blogs that are connected by a reference has to cover different topics because otherwise, the readers can notice that they are split just for more contribution. Set of blogs and bidirectional references between some pairs of them is called blogs network.

There are n different topics, numbered from 1 to n sorted by Johnny's knowledge. The structure of the blogs network is already prepared. Now Johnny has to write the blogs in some order. He is lazy, so each time before writing a blog, he looks at it's already written neighbors (the blogs referenced to current one) and chooses the topic with the smallest number which is not covered by neighbors. It's easy to see that this strategy will always allow him to choose a topic because there are at most n−1 neighbors.

For example, if already written neighbors of the current blog have topics number 1, 3, 1, 5, and 2, Johnny will choose the topic number 4 for the current blog, because topics number 1, 2 and 3 are already covered by neighbors and topic number 4 isn't covered.

As a good friend, you have done some research and predicted the best topic for each blog. Can you tell Johnny, in which order he has to write the blogs, so that his strategy produces the topic assignment chosen by you?

Input

The first line contains two integers n (1≤n≤5⋅105) and m (0≤m≤5⋅105) — the number of blogs and references, respectively.

Each of the following m lines contains two integers a and b (a≠b; 1≤a,b≤n), which mean that there is a reference between blogs a and b. It's guaranteed that the graph doesn't contain multiple edges.

The last line contains n integers t1,t2,…,tn, i-th of them denotes desired topic number of the i-th blog (1≤ti≤n).

Output

If the solution does not exist, then write −1. Otherwise, output n distinct integers p1,p2,…,pn (1≤pi≤n), which describe the numbers of blogs in order which Johnny should write them. If there are multiple answers, print any.

Examples

input1

3 3
1 2
2 3
3 1
2 1 3

output1

2 1 3

input2

3 3
1 2
2 3
3 1
1 1 1

output2

-1

input3

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

output3

2 5 1 3 4

Note

In the first example, Johnny starts with writing blog number 2, there are no already written neighbors yet, so it receives the first topic. Later he writes blog number 1, it has reference to the already written second blog, so it receives the second topic. In the end, he writes blog number 3, it has references to blogs number 1 and 2 so it receives the third topic.

Second example: There does not exist any permutation fulfilling given conditions.

Third example: First Johnny writes blog 2, it receives the topic 1. Then he writes blog 5, it receives the topic 1 too because it doesn't have reference to single already written blog 2. Then he writes blog number 1, it has reference to blog number 2 with topic 1, so it receives the topic 2. Then he writes blog number 3 which has reference to blog 2, so it receives the topic 2. Then he ends with writing blog number 4 which has reference to blog 5 and receives the topic 2.

---

E. Johnny and Grandmaster

》英文原题《

---

F. Johnny and Megan's Necklace

》英文原题《