Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

Description

Input

第一行为N、M，其中 表示顶点的数目， 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行，每行三个整数Ui，Vi，Wi，表示顶点Ui与Vi之间有一条边，其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行，每行两个整数Xi、Yi，表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

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

Sample Output

8

【样例说明】 边(4,6)的权由7修改为3，代价为4
边(1,2)的权由2修改为3，代价为1
边(1,5)的权由1修改为4，代价为3
所以总代价为4+1+3=8
修改方案不唯一。

HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权

题解

这道题的题意是要求修改一些边的权值使得给出的树成为这个图的最小生成树，求最小代价。
注意到我们只可能增大非树边，减小树边。

那么对于一个树边ii和一个可能影响到最小生成树的非树边jj，我们一定要满足如下条件：
wi−di≤wj+djwi−di≤wj+dj
移项，即
wi−wj≤di+djwi−wj≤di+dj
其中d表示我们对于边的改动值（一定非负）
这样就可以转化成二分图最小顶标和来做。
我们把边看成点，两原边边权之差作为新点之间的边权，跑一边KM或者最小费用最大流就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5

差分约束系统

一、何为差分约束系统：
差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说，差分约束系统就是一些不等式的组，而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如：

二、差分约束系统的求解：
差分约束系统可以转化为图论来解决，对应于上面的不等式组，如果要求出x3-x0的最大值的话，叠加不等式可以推导出x3-x0<=7,最大值即为7，我们可以通过建立一个图，包含6个顶点，对每个xj-xi<=bk，建立一条i到j的有向边，权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7，这是巧合吗？并不是。
之所以差分约束系统可以通过图论的最短路来解，是因为xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式：（在此引用大牛的博客）
B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
 如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c),而这正对应了下图中C到A的最短路。

因此，对三角不等式加以推广，变量n个，不等式m个，要求xn-x1的最大值，便就是求取建图后的最短路。
同样地，如果要求取差分约束系统中xn-x1的最小值，便是求取建图后的最长路。最长路可以通过spfa求出来，只需要改下松弛的方向即可，即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负，求取最短路，两者是等价的。
最长路求解算法证明如下：
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点，建图后不一定存在最短路/最长路，因为可能存在无限减小/增大的负环/正环，题

Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

Description

You are given array ai of length n. You may consecutively apply two operations to this array:
·remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
·change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ a_i

Description

Piegirl found the red button. You have one last chance to change the inevitable end.
The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once.
Your task is to find any such order and print it. If there is no such order, print -1.

Input

Input consists of a single integer n (2 ≤ n ≤ 105).

Output

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

Examples

Input

2

Output

0 1 0

Input

3

Output

-1

Input

4

Output

0 1 3 2 0

Input

16

Output

0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

题目大意

有n个红色按钮，编号0，1，……，n，你需要从0开始按这些红色按钮，要求除0号以外都只能按一次，而且是从0按，最后一次也要

三分法

我们已经学过有序序列查找元素的二分法了，那么这次来学一下三分法。
三分法，故名思义，就是把一个区间分成三份。
但是这三分法是用来干什么的呢？
三分法是用来求解单峰函数型(凸型序列，包括上凸和下凸)查找元素问题最值的有力手段。

(图片转自chenxiaoran666的博客)

三分的核心思路如下： 对于当前的区间[l,r]，求出midl = (l+r)/2,midr = (midl+r)/2,比较f(midl)与f(midr)的值哪个更接近于最值,并根据结果确认下一个搜索区间是[l,midr]还是[midl,r]，直到l>=r。

示例代码

我们以上凸序列为例

int find(int l,int r){
    if(l >= r)return l;
    int midl = (l+r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        return find(l,midr);
    else return find(midl,r);
}​

当然也是可以写成迭代形式的，如下：

while(l < r){
    int midl = (l + r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        r = midr;
    else l = midl;
}​

虽然很少用，但是这种方法还是会有些用的，例如凸包。

如果各位官爷学到的话，请在我的QQ点个赞吧，QQ932901730（厚脸皮）。

数位DP

这个鬼东西是个啥？？？？我咋没见过呢?
emmm……
数位DP，顾名思义，利用数字的每一个数位（个、十、百、千、万、……）来计算的动态规划算法。
啥？我还是不懂的？
那么我们还是来说一下这种算法的适用题型吧……
给定两个数a，b，求满足给定条件的数的个数。（举个栗子：求ab之间不包含子串“62”的数的个数）
这也太明显了吧……按照一个个把数字拆开检查不就行了么……
nope！ 如果是a，b的范围是$1<=a,b<=20000000000$呢？你还暴力拆开检查么？你家计算机跑上一天都不一定能跑出来。
那咋整？
数位DP！
数位DP的基本思路就是按照数位对数字进行拆开，但是数位DP会利用每一位的数进行动态规划从而达到消除重复计算的作用，从而减小时间复杂度。像是上面的例子，我们可以想象，其实我们计算很多数的时候是在进行一些不必要的重复计算的。而数位DP就是为了这类问题避开这些重复计算而被总结设计出来的。
下面我们来说一下数位DP的核心步骤。
枚举当前是第几位，然后枚举这一位上的数，再枚举这个的低一位的数，检查是否满足条件，进行状态转移。这一步的伪代码如下

void init(){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= 9;++i)
        dp[1][i] = 1;
    for(int i = 2;i <= 10;++i)
        for(int j = 0;j <= 9;++j)
            for(int k = 0;k <= 9;++k){
                if(满足题目条件)
                    dp[i][j] += dp[i-1][k];
            }
    return;
}

对数位DP数组计算完成后，对于题中的a，b，我们就只需要计算0——b中满足题目条件的数的个数和0——a-1中满足题目条件的个数，然后相减就可以得到我们想要的结果了。（差分前缀和的思想）一般来说这一步的代码是比较固定的，大致如下，具体题目自己调整。

long long solve(long long x){
    long long ans = 0;
    k = 0;
    memset(m,0,sizeof(m

6 个技巧，提升 C++11 的 vector 性能

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};

// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVect