結果
| 問題 |
No.382 シャイな人たち (2)
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2016-09-10 01:48:02 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 676 ms / 8,000 ms |
| コード長 | 24,485 bytes |
| コンパイル時間 | 5,229 ms |
| コンパイル使用メモリ | 92,856 KB |
| 実行使用メモリ | 48,680 KB |
| 最終ジャッジ日時 | 2024-11-16 19:34:10 |
| 合計ジャッジ時間 | 17,811 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 |
ソースコード
package q3xx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;
public class N382_3 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
long S = ni();
S = S * 12345 % 1000003;
int n = (int)(S%120)+2;
S = S * 12345 % 1000003;
int p = (int)S;
int m = (n>>>6)+1;
long[][] g = new long[n][m];
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
S = S * 12345 % 1000003;
if(S < p){
g[i][j>>>6] |= 1L<<j;
g[j][i>>>6] |= 1L<<i;
}
}
}
int[] res = MCS(g, TL);
if(2 <= res.length+1 && res.length+1 <= n){
out.println(res.length+1);
for(int i = 0;i < res.length;i++){
if(i > 0)out.print(" ");
out.print(res[i]+1);
}
out.println();
}else{
out.println(-1);
}
}
private static final int TL = 9000;
private static final int STRICT_THRESHOLD = 200;
private static final int LOCAL_SEARCH_CO = 5;
private static final int INITIAL_SAMPLE_FIXED_THRESHOLD = 200;
private static final int NUM_INITIAL_SAMPLE = 5;
private static final int NUM_INITIAL_SAMPLE_BASE = 300000;
public static boolean[] process(int[][] g, long S)
{
int n = g.length;
int[] orig = new int[n]; for(int i = 0;i < n;i++)orig[i] = i;
boolean[] is = new boolean[n];
// remove duplicate edges
for(int j = 0;j < g.length;j++){
Arrays.sort(g[j]);
g[j] = uniq(g[j]);
}
// remove degree 0 nodes
{
FilterResult fres = removeTrivialNodes(g, is, orig);
for(int i = 0;i < g.length;i++){
if(fres.map[i] != -1)orig[fres.map[i]] = orig[i];
}
g = fres.fg;
}
// remove trivial(degree 1) edges
FilterResult fres = removeTrivialEdges(g, is, orig);
if(fres != null){
for(int i = 0;i < g.length;i++){
if(fres.map[i] != -1)orig[fres.map[i]] = orig[i];
}
g = fres.fg;
}
SplitResult sr = split(g);
int nbig = 0;
for(int[] b : sr.buckets){
if(b.length > STRICT_THRESHOLD)nbig++;
}
for(int i = 0;i < sr.buckets.length;i++){
int[] b = sr.buckets[i];
int[][] sg = sr.sg[i];
if(b.length == 0)continue;
if(b.length <= 2){
is[orig[b[0]]] = true;
continue;
}
if(b.length <= STRICT_THRESHOLD){
long[][] fg = flip(sparseToPacked(sg));
int[] mc = MCS(fg, TL);
for(int x : mc)is[orig[b[x]]] = true;
}
}
long G = System.currentTimeMillis();
long tl = nbig == 0 ? 0 : (TL-(G-S))/nbig;
for(int i = 0;i < sr.buckets.length;i++){
int[] b = sr.buckets[i];
int[][] sg = sr.sg[i];
if(b.length > STRICT_THRESHOLD){
// exact
S = System.currentTimeMillis();
long[][] fg = flip(sparseToPacked(sg));
int[] mc = MCS(fg, tl);
for(int x : mc)is[orig[b[x]]] = true;
}
}
return is;
}
private static FilterResult removeTrivialNodes(int[][] g, boolean[] is, int[] orig)
{
int n = g.length;
boolean[] filter = new boolean[n];
for(int i = 0;i < n;i++){
filter[i] = g[i].length > 0;
if(g[i].length == 0){
is[orig[i]] = true;
}
}
return filter(filter, g);
}
private static FilterResult removeTrivialEdges(int[][] g, boolean[] is, int[] orig)
{
int n = g.length;
int[] degs = new int[n];
for(int i = 0;i < n;i++)degs[i] = g[i].length;
boolean[] ved = new boolean[n];
int[] q = new int[n];
int p = 0;
for(int i = 0;i < n;i++){
if(degs[i] == 1){
q[p++] = i;
ved[i] = true;
}
}
if(p == 0)return null;
for(int r = 0;r < p;r++){
int cur = q[r];
if(degs[cur] < 1){
// killed node
degs[cur] = -1;
for(int e : g[cur]){
if(!ved[e] && --degs[e] == 1){
ved[e] = true;
q[p++] = e;
}
}
}else{
// stand node
assert degs[cur] == 1;
degs[cur] = -1;
is[orig[cur]] = true;
for(int e : g[cur]){
degs[e] = -1; // even if e=stand node, kill.
if(!ved[e]){
ved[e] = true;
q[p++] = e;
}
}
}
}
boolean[] alive = new boolean[n];
for(int i = 0;i < n;i++)alive[i] = degs[i] >= 0;
return filter(alive, g);
}
public static FilterResult filter(boolean[] f, int[][] g)
{
int n = g.length;
int[] map = new int[n];
Arrays.fill(map, -1);
int p = 0;
for(int i = 0;i < n;i++){
if(f[i])map[i] = p++;
}
int[][] h = new int[p][];
int m = 0;
for(int i = 0;i < n;i++)m = Math.max(m, g[i].length);
int[] temp = new int[m+1];
for(int i = 0;i < n;i++){
if(f[i]){
int q = 0;
for(int e : g[i]){
if(f[e])temp[q++] = map[e];
}
h[map[i]] = Arrays.copyOf(temp, q);
}
}
FilterResult ret = new FilterResult();
ret.map = map;
ret.fg = h;
return ret;
}
public static class FilterResult
{
int[][] fg;
int[] map;
}
private static long[][] flip(long[][] g)
{
int n = g.length;
for(int i = 0;i < n;i++){
for(int j = 0;j < n>>>6;j++){
g[i][j] = ~g[i][j];
}
g[i][n>>>6] ^= (1L<<n)-1;
}
return g;
}
private static long[][] sparseToPacked(int[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
long[][] pg = new long[n][m];
for(int i = 0;i < n;i++){
for(int e : g[i]){
pg[i][e>>>6] |= 1L<<e;
}
}
return pg;
}
public static class DJSet {
public int[] upper;
public DJSet(int n) {
upper = new int[n];
Arrays.fill(upper, -1);
}
public int root(int x) {
return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
}
public boolean equiv(int x, int y) {
return root(x) == root(y);
}
public boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (upper[y] < upper[x]) {
int d = x;
x = y;
y = d;
}
upper[x] += upper[y];
upper[y] = x;
}
return x == y;
}
public int count() {
int ct = 0;
for (int u : upper)
if (u < 0)
ct++;
return ct;
}
}
public static SplitResult split(int[][] g)
{
int n = g.length;
DJSet ds = new DJSet(n);
for(int i = 0;i < n;i++){
for(int e : g[i]){
ds.union(i, e);
}
}
int cid = 0;
int[] clus = new int[n];
for(int i = 0;i < n;i++){
if(ds.upper[i] < 0)clus[i] = cid++;
}
for(int i = 0;i < n;i++){
clus[i] = clus[ds.root(i)];
}
int[][] buckets = makeBuckets(clus, cid);
int[] iind = new int[n];
for(int[] b : buckets){
for(int i = 0;i < b.length;i++){
iind[b[i]] = i;
}
}
int[][][] sg = new int[cid+1][][];
for(int i = 0;i < cid+1;i++){
sg[i] = new int[buckets[i].length][];
for(int j = 0;j < buckets[i].length;j++){
int cur = buckets[i][j];
sg[i][j] = new int[g[cur].length];
for(int k = 0;k < g[cur].length;k++){
sg[i][j][k] = iind[g[cur][k]];
}
}
}
SplitResult ret = new SplitResult();
ret.sg = sg;
ret.buckets = buckets;
return ret;
}
public static class SplitResult
{
public int[][] buckets;
public int[][][] sg;
}
public static int[][] makeBuckets(int[] a, int sup)
{
int n = a.length;
int[][] bucket = new int[sup+1][];
int[] bp = new int[sup+1];
for(int i = 0;i < n;i++)bp[a[i]]++;
for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
return bucket;
}
public static int[] uniq(int[] a)
{
int n = a.length;
int p = 0;
for(int i = 0;i < n;i++) {
if(i == 0 || a[i] != a[i-1])a[p++] = a[i];
}
return p == n ? a : Arrays.copyOf(a, p);
}
static int size(boolean[] a)
{
int ret = 0;
for(boolean v : a)if(v)ret++;
return ret;
}
public static class XorShift extends Random {
private static final long serialVersionUID = 6806629989739663134L;
private long x=123456789, y=362436069, z=521288629, w=88675123;
public XorShift() {super(); x = System.nanoTime();}
public XorShift(long seed) {super(seed); x = seed;}
public synchronized void setSeed(long seed) {super.setSeed(seed); x = seed;}
protected int next(int bits){
long t=(x^x<<11)&(1L<<32)-1; x=y; y=z; z=w; w=(w^w>>>19^t^t>>>8)&(1L<<32)-1;
return (int)w>>>32-bits;
}
}
public static int[] MCS(long[][] g, long timeout)
{
long S = System.currentTimeMillis();
int n = g.length;
int m = (n>>>6)+1;
if(n == 0)return new int[0];
long[] Qmax = new long[m];
int[] no = new int[n];
int[] V = new int[n];
extendedInitialSortNumber(V, no, Qmax, g);
long[] nQmax = new long[m];
for(int i = 0;i < n;i++)if(Qmax[V[i]>>>6]<<~V[i]<0)nQmax[i>>>6] |= 1L<<i;
int[] nno = new int[n];
for(int i = 0;i < n;i++)nno[i] = no[V[i]];
long[][] ng = new long[n][m];
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
if(g[V[i]][V[j]>>>6]<<~V[j]<0){
ng[i][j>>>6] |= 1L<<j;
ng[j][i>>>6] |= 1L<<i;
}
}
}
long[] nv = new long[m];
fill(nv, n);
int[] nr = new int[n];
for(int i = 0;i < n;i++)nr[i] = i;
nos = new int[n][n];
nos[0] = nno;
C = new long[n+2][m];
// {
// int[] rec = reconstruct(nQmax, V);
// check(rec, g);
// }
// tr(System.currentTimeMillis() - S, size(nQmax));
try {
expandS(nv, nr, 0, new long[m], nQmax, ng, S+timeout);
} catch (Exception e) {
}
int[] rec = reconstruct(nQmax, V);
return rec;
}
private static int[] reconstruct(long[] Qmax, int[] V)
{
int m = size(Qmax);
int[] ret = new int[m];
int p = 0;
for(int i = 0;i < Qmax.length;i++){
for(long j = Qmax[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
ret[p++] = V[id];
}
}
assert p == m;
Arrays.sort(ret);
return ret;
}
private static void fill(long[] a, int n)
{
for(int i = 0;i < a.length && i < n>>>6;i++){
a[i] = -1L;
}
if((n&63) != 0)a[n>>>6] = (1L<<n)-1;
}
private static int[][] nos;
private static int[] add = new int[100000];
private static int ap;
private static void expandS(long[] Va, int[] R, int depno, long[] Q, long[] Qmax, long[][] g, long expired)
{
int n = g.length;
int m = (n>>>6)+1;
if(System.currentTimeMillis() > expired)throw new RuntimeException();
int[] no = nos[depno];
for(int j = R.length-1;j >= 0;j--){
int p = R[j];
assert no[p] >= 1;
if(depno == 0 || size(Q) + no[p] > size(Qmax)){
Q[p>>>6] |= 1L<<p;
Va[p>>>6] ^= 1L<<p;
long[] Vp = new long[Va.length];
for(int k = 0;k < m;k++){
Vp[k] = Va[k]&g[p][k];
}
if(!empty(Vp)){
ap = 0;
int res = renumberSortLight(Vp, g);
int[] ladds = Arrays.copyOf(add, ap);
for(int ladd : ladds){
assert Q[ladd>>>6]<<~ladd>=0;
assert Vp[ladd>>>6]<<~ladd<0;
Q[ladd>>>6] ^= 1L<<ladd;
Vp[ladd>>>6] ^= 1L<<ladd;
}
if(size(Q) > size(Qmax)){
for(int kk = 0;kk < Qmax.length;kk++)Qmax[kk] = Q[kk];
}
int[] newR = new int[size(Vp)];
int[] newNo = nos[depno+1];
int k = renumberSort(Vp, newR, newNo, g, size(Qmax)-size(Q));
newR = Arrays.copyOfRange(newR, k, newR.length);
expandS(Vp, newR, depno+1, Q, Qmax, g, expired);
for(int ladd : ladds){
assert Q[ladd>>>6]<<~ladd<0;
Q[ladd>>>6] ^= 1L<<ladd;
Vp[ladd>>>6] ^= 1L<<ladd;
}
}else if(size(Q) > size(Qmax)){
for(int k = 0;k < Qmax.length;k++)Qmax[k] = Q[k];
}
Q[p>>>6] ^= 1L<<p;
}else{
if(depno > 0)break; // If we are not at the first level of recursion return from recursion because the candidates are ordered by colours and all the remaining candidates have a smaller colour number.
}
}
}
private static int renumberSortLight(long[] Va, long[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
int maxno = 0;
for(int z = 0;z < m;z++){
for(long y = Va[z];y != 0;y&=y-1){
int p = Long.numberOfTrailingZeros(y)|z<<6;
// Conventional greedy approximate coloring
int k = 1;
inner:
while(k <= maxno){
for(int i = 0;i < m;i++){
if((g[p][i]&C[k][i]) != 0){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
Arrays.fill(C[k], 0L);
}
C[k][p>>>6] |= 1L<<p;
}
}
inner:
for(int k = 1;k <= maxno;k++){
if(size(C[k]) == 1){
// If there are candidates having a unique colour, check each of them if it is adjacent to all the candidates with a smaller colour.
int id = first(C[k]);
assert Va[id>>>6]<<~id<0;
for(int l = 0;l < m;l++){
long row = g[id][l];
if(id>>>6 == l)row ^= 1L<<id;
if((Va[l]&row) == Va[l]){
}else{
continue inner;
}
}
// If yes, then add such vertices to the current clique and remove them from S'
add[ap++] = id;
}
}
return 0;
}
public static int first(long[] a)
{
int offset = 0;
for(long v : a){
if(v != 0)return offset + Long.numberOfTrailingZeros(v);
offset += 64;
}
return -1;
}
private static void ReNUMBER(int p, int[] no, int nop, int noth, long[][] c, long[][] g)
{
int n = g.length;
int m = (n>>>6)+1;
for(int k1 = 1;k1 <= noth-1;k1++){
int inter = 0;
int q = -1;
for(int i = 0;i < m;i++){
long inte = g[p][i]&c[k1][i];
int icb = Long.bitCount(inte);
inter += icb;
if(inter >= 2)break;
if(icb == 1){
q = Long.numberOfTrailingZeros(inte)|i<<6;
}
}
if(inter == 1){
assert q != -1;
inner:
for(int k2 = k1 + 1;k2 <= noth;k2++){
for(int i = 0;i < m;i++){
if((g[q][i]&c[k2][i]) != 0)continue inner;
}
no[q] = k2;
no[p] = k1;
assert p != q;
assert c[nop][p>>>6]<<~p<0;
assert c[k1][p>>>6]<<~p>=0;
assert c[k1][q>>>6]<<~q<0;
assert c[k2][q>>>6]<<~q>=0;
c[nop][p>>>6] ^= 1L<<p;
c[k1][p>>>6] ^= 1L<<p;
c[k1][q>>>6] ^= 1L<<q;
c[k2][q>>>6] ^= 1L<<q;
return;
}
}
}
}
private static long[][] C;
// in: Va, noth
// out: R,no
private static int renumberSort(long[] Va, int[] R, int[] no, long[][] g, int noth)
{
// Arrays.fill(R, -1);
// Arrays.fill(no, -1);
int n = g.length;
int m = (n>>>6)+1;
int maxno = 0;
for(int z = 0;z < m;z++){
for(long y = Va[z];y != 0;y&=y-1){
int p = Long.numberOfTrailingZeros(y)|z<<6;
// Conventional greedy approximate coloring
int k = 1;
inner:
while(k <= maxno){
for(int i = 0;i < m;i++){
if((g[p][i]&C[k][i]) != 0){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
Arrays.fill(C[k], 0L);
}
no[p] = k;
C[k][p>>>6] |= 1L<<p;
// Re-NUMBER
if(k > noth && k == maxno){
ReNUMBER(p, no, k, noth, C, g);
if(empty(C[maxno])){
maxno--;
}
}
}
}
int i = size(Va);
if(noth < 0)noth = 0;
int k;
for(k = maxno;k >= noth+1;k--){
for(int j = m-1;j >= 0;j--){
for(long y = C[k][j];y != 0;y^=Long.highestOneBit(y)){
int x = j<<6|63-Long.numberOfLeadingZeros(y);
i--;
R[i] = x;
no[R[i]] = k;
}
}
}
if(i != 0){
k--;
for(int j = m-1;j >= 0;j--){
if(C[k][j] != 0){
int x = j<<6|63-Long.numberOfLeadingZeros(C[k][j]);
i--;
R[i] = x;
no[R[i]] = noth;
break;
}
}
}
return i;
}
public static int size(long[] a)
{
int ret = 0;
for(long v : a)ret += Long.bitCount(v);
return ret;
}
public static boolean empty(long[] a)
{
for(long v : a)if(v != 0)return false;
return true;
}
public static int min(long[] a)
{
for(int i = 0;i < a.length;i++){
if(a[i] != 0L)return Long.numberOfTrailingZeros(a[i])|i<<6;
}
return -1;
}
private static void extendedInitialSortNumber(int[] V, int[] no, long[] Qmax, long[][] g)
{
int n = g.length;
int[] degs = new int[n];
int maxdeg = 0;
for(int i = 0;i < n;i++){
degs[i] = size(g[i]);
maxdeg = Math.max(maxdeg, degs[i]);
}
// SORT
long[] R = new long[(n>>>6)+1];
fill(R, n);
int vp = n;
long[] Rmin = rmin(R, degs);
while(size(Rmin) != size(R)){
int p = min(Rmin);
if(size(Rmin) >= 2){
int minv = Integer.MAX_VALUE;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
int lv = exdeg(id, degs, g);
if(lv < minv){
minv = lv;
p = id;
}
}
}
}
V[--vp] = p;
R[p>>>6] ^= 1L<<p;
for(int i = 0;i < R.length;i++){
for(long j = R[i]&g[p][i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
degs[id]--;
}
}
Rmin = rmin(R, degs);
}
// Regular subgraph
numberSort(Rmin, no, g);
int ii = 0;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
V[ii++] = id;
}
}
// NUMBER
NUMBER: {
int m = 0;
for(int i = 0;i < Rmin.length;i++){
for(long j = Rmin[i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
m = Math.max(m, no[id]);
}
}
int mmax = size(Rmin) + maxdeg - m;
m++;
for(int i = size(Rmin);i < mmax;i++){
if(i >= n)break NUMBER;
no[V[i]] = m++;
}
for(int i = mmax;i < n;i++){
no[V[i]] = maxdeg + 1;
}
}
// START
if(n >= 4){
Random gen = new XorShift();
long[][] fg = new long[n][];
for(int i = 0;i < n;i++){
fg[i] = Arrays.copyOf(g[i], g[i].length);
}
fg = flip(fg);
long[] is = new long[(n>>>6)+1];
int lim = n <= INITIAL_SAMPLE_FIXED_THRESHOLD ? NUM_INITIAL_SAMPLE : NUM_INITIAL_SAMPLE_BASE/n/((n>>>6)+1);
for(int rep = 0;rep < lim;rep++){
long[] can = initialSample(fg, gen);
if(size(can) > size(is)){
is = can;
}
}
for(int i = 0;i < is.length;i++){
Qmax[i] = is[i];
}
}
}
private static long[] initialSample(long[][] g, Random gen)
{
int n = g.length;
long[] a = new long[n];
for(int i = 0;i < n;i++){
int deg = size(g[i]);
a[i] = (long)gen.nextInt((int)Math.min(2000000000L, deg*deg*100L)+1)<<32|i;
}
Arrays.sort(a);
int m = (n>>>6)+1;
long[] is = new long[m];
long[] temp = new long[m];
outer:
for(int i = 0;i < n;i++){
int cur = (int)a[i];
for(int j = 0;j < m;j++){
if((g[cur][j]&is[j]) != 0)continue outer;
}
is[cur>>>6] |= 1L<<cur;
}
// local search
int[] iss = new int[n];
int ip = 0;
int[] covered = new int[n];
long[] c1 = new long[m];
long[] c0 = new long[m];
for(int i = 0;i < n;i++){
if(is[i>>>6]<<~i<0){
iss[ip++] = i;
add(i, 1, covered, g, c0, c1);
}
}
if(ip == 0)return is;
for(int i = 0;i < n;i++){
if(covered[i] == 0){
c0[i>>>6] |= 1L<<i;
}else if(covered[i] == 1){
c1[i>>>6] |= 1L<<i;
}
}
for(int rep = 0;rep < LOCAL_SEARCH_CO*n;rep++){
int ind = gen.nextInt(ip);
int id = iss[ind];
for(int j = 0;j < m;j++){ // id's neighbor and covered by one.
temp[j] = c1[j]&g[id][j]&~is[j];
}
int szt = size(temp);
if(szt == 0)continue;
if(szt >= 2 && gen.nextInt(3) == 0){
int u = select(temp, gen.nextInt(szt));
assert temp[u>>>6]<<~u<0;
temp[u>>>6] ^= 1L<<u;
for(int j = 0;j < m;j++){
temp[j] &= ~g[u][j];
}
szt = size(temp);
if(szt == 0)continue;
int v = select(temp, gen.nextInt(size(temp)));
assert is[id>>>6]<<~id<0;
assert is[u>>>6]<<~u>=0;
assert is[v>>>6]<<~v>=0;
is[id>>>6] ^= 1L<<id;
is[u>>>6] ^= 1L<<u;
is[v>>>6] ^= 1L<<v;
iss[ind] = u;
iss[ip++] = v;
add(id, -1, covered, g, c0, c1);
add(u, 1, covered, g, c0, c1);
add(v, 1, covered, g, c0, c1);
continue;
}
int u = select(temp, gen.nextInt(szt));
assert is[u>>>6]<<~u>=0;
is[id>>>6] ^= 1L<<id;
is[u>>>6] ^= 1L<<u;
add(id, -1, covered, g, c0, c1);
add(u, 1, covered, g, c0, c1);
iss[ind] = u;
}
// if(n >= 150)tr(O, "=>", size(is));
return is;
}
static int select(long[] a, int K)
{
int offset = 0;
for(long v : a){
int bc = Long.bitCount(v);
if(K < bc){
for(int i = 0;i < K;i++)v &= v-1;
return Long.numberOfTrailingZeros(v) + offset;
}else{
K -= bc;
offset += 64;
}
}
return -1;
}
private static void add(int i, int plus, int[] covered, long[][] g, long[] c0, long[] c1)
{
int m = (g.length>>>6)+1;
if(covered[i] == 1)c1[i>>>6] ^= 1L<<i;
if(covered[i] == 0)c0[i>>>6] ^= 1L<<i;
covered[i] += plus;
if(covered[i] == 1)c1[i>>>6] ^= 1L<<i;
if(covered[i] == 0)c0[i>>>6] ^= 1L<<i;
for(int j = 0;j < m;j++){
for(long x = g[i][j];x != 0;x&=x-1){
int id = Long.numberOfTrailingZeros(x)|j<<6;
if(covered[id] == 1)c1[id>>>6] ^= 1L<<id;
if(covered[id] == 0)c0[id>>>6] ^= 1L<<id;
covered[id] += plus;
if(covered[id] == 1)c1[id>>>6] ^= 1L<<id;
if(covered[id] == 0)c0[id>>>6] ^= 1L<<id;
}
}
}
private static int exdeg(int q, int[] degs, long[][] g)
{
int ret = 0;
for(int i = 0;i < g[q].length;i++){
for(long j = g[q][i];j != 0;j&=j-1){
int id = Long.numberOfTrailingZeros(j)|i<<6;
ret += degs[id];
}
}
return ret;
}
private static long[] rmin(long[] R, int[] degs)
{
int mindeg = 9999;
long[] Rmin = new long[R.length];
for(int i = 0;i < R.length;i++){
for(long j = R[i];j != 0;j&=j-1){
int v = Long.numberOfTrailingZeros(j)|i<<6;
if(degs[v] < mindeg){
mindeg = degs[v];
Rmin[v>>>6] |= 1L<<v;
}else if(degs[v] == mindeg){
Arrays.fill(Rmin, 0L);
Rmin[v>>>6] |= 1L<<v;
}
}
}
return Rmin;
}
private static void numberSort(long[] R, int[] no, long[][] g)
{
int n = g.length;
int maxno = 0;
int m = (n>>>6)+1;
long[][] c = new long[size(R)+1][m];
for(int z = 0;z < R.length;z++){
for(long j = R[z];j != 0;j &= j-1){
int p = Long.numberOfTrailingZeros(j)|z<<6;
int k = 1;
inner:
while(true){
for(int i = 0;i < m;i++){
if((g[p][i]&c[k][i]) != 0){
k++;
continue inner;
}
}
break;
}
if(k > maxno){
maxno = k;
}
no[p] = k;
c[k][p>>>6] |= 1L<<p;
}
}
// sort
int i = 0;
for(int k = 1;k <= maxno;k++){
for(int u = 0;u < m;u++){
for(long j = c[k][u];j != 0;j &= j-1){
int p = Long.numberOfTrailingZeros(j)|u<<6;
i++;
R[p>>>6] |= 1L<<p;
}
}
}
assert i == size(R);
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new N382_3().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}