#![allow(unused_imports)] use input::*; use std::{ collections::*, io::{self, BufWriter, Write}, }; fn run(mut ss: I, mut out: O) { use random::*; let t: i32 = ss.parse(); let mut rng = Xoshiro::seed_from_u64(1959); for _ in 0..t { let n: usize = ss.parse(); let b: Vec = (0..n) .map(|_| loop { let x: u32 = rng.range(0, 1 << 10); if x.count_ones() == 5 { break x; } }) .collect(); let mut ans = vec![0; n]; for q in 0..10 { w!(out, "?"); for &b in &b { w!(out, " {}", (b >> q) & 1); } wln!(out); out.flush().unwrap(); let mut prev = 0; for (a, ans) in ss.seq::().take(n).zip(&mut ans) { if a != prev { *ans = a; } prev = a; } } w!(out, "!"); for ans in ans { w!(out, " {}", ans); } wln!(out); out.flush().unwrap(); } } fn main() { let stdin = io::stdin(); let ss = SplitWs::new(stdin.lock()); let stdout = io::stdout(); let out = BufWriter::new(stdout.lock()); run(ss, out); } pub mod random { mod pcg { use super::{RngCore, SeedableRng}; #[doc = " PCG-XSH-RR"] #[derive(Clone, Copy, PartialEq, Eq, Debug)] pub struct Pcg(u64); const MUL: u64 = 5129263795064623965; const INC: u64 = 4280768313201238837; impl SeedableRng for Pcg { fn seed_from_u64(seed: u64) -> Self { Self(seed.wrapping_add(INC)) } } impl RngCore for Pcg { fn next_u32(&mut self) -> u32 { let mut x = self.0; self.0 = x.wrapping_mul(MUL).wrapping_add(INC); x ^= x >> 18; ((x >> 27) as u32).rotate_right((x >> 59) as u32) } fn next_u64(&mut self) -> u64 { (self.next_u32() as u64) << 32 | self.next_u32() as u64 } } } mod xoshiro { use super::{RngCore, SeedableRng}; #[doc = " "] #[derive(Clone, Copy, PartialEq, Eq, Debug)] pub struct Xoshiro([u64; 4]); impl Xoshiro { pub fn from_seed(seed: [u64; 4]) -> Self { Self(seed) } } impl SeedableRng for Xoshiro { fn seed_from_u64(seed: u64) -> Self { let mut sm = SplitMix::seed_from_u64(seed); let mut state = [0; 4]; for s in &mut state { *s = sm.next_u64(); } Self::from_seed(state) } } impl RngCore for Xoshiro { fn next_u32(&mut self) -> u32 { (self.next_u64() >> 32) as u32 } fn next_u64(&mut self) -> u64 { let res = (self.0[0].wrapping_add(self.0[3])) .rotate_left(23) .wrapping_add(self.0[0]); let t = self.0[1] << 17; self.0[2] ^= self.0[0]; self.0[3] ^= self.0[1]; self.0[1] ^= self.0[2]; self.0[0] ^= self.0[3]; self.0[2] ^= t; self.0[3] = self.0[3].rotate_left(45); res } } #[doc = " "] #[derive(Clone, Copy, PartialEq, Eq, Debug)] pub struct SplitMix(u64); impl SeedableRng for SplitMix { fn seed_from_u64(seed: u64) -> Self { Self(seed) } } impl RngCore for SplitMix { fn next_u32(&mut self) -> u32 { (self.next_u64() >> 32) as u32 } fn next_u64(&mut self) -> u64 { self.0 = self.0.wrapping_add(0x9e3779b97f4a7c15); let mut z = self.0; z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9); z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb); z ^ (z >> 31) } } } pub use self::pcg::Pcg; pub use self::xoshiro::*; pub trait RngCore { fn next_u32(&mut self) -> u32; fn next_u64(&mut self) -> u64; } pub trait Rng: RngCore { fn gen(&mut self) -> T { T::sample(self) } fn range(&mut self, l: T, r: T) -> T { T::range(self, l, r) } fn range_inclusive(&mut self, l: T, r: T) -> T { T::range_inclusive(self, l, r) } fn gen_bool(&mut self, p: f64) -> bool { if p >= 1. { return true; } self.next_u64() < (2.0f64.powi(64) * p) as u64 } fn open01(&mut self) -> T { T::open01(self) } fn standard_normal(&mut self) -> T { T::standard_normal(self) } fn normal(&mut self, mean: T, sd: T) -> T { T::normal(self, mean, sd) } fn exp(&mut self, lambda: T) -> T { T::exp(self, lambda) } fn shuffle(&mut self, a: &mut [T]) { for i in (1..a.len()).rev() { a.swap(self.range_inclusive(0, i), i); } } fn partial_shuffle<'a, T>( &mut self, a: &'a mut [T], n: usize, ) -> (&'a mut [T], &'a mut [T]) { let n = n.min(a.len()); for i in 0..n { a.swap(i, self.range(i, a.len())); } a.split_at_mut(n) } fn choose<'a, T>(&mut self, a: &'a [T]) -> &'a T { assert!(!a.is_empty()); &a[self.range(0, a.len())] } fn choose_mut<'a, T>(&mut self, a: &'a mut [T]) -> &'a mut T { assert!(!a.is_empty()); &mut a[self.range(0, a.len())] } } impl Rng for T {} pub trait Sample { fn sample(rand: &mut T) -> Self; } pub trait Uniform { fn range(rand: &mut T, l: Self, r: Self) -> Self; fn range_inclusive(rand: &mut T, l: Self, r: Self) -> Self; } pub trait SampleFloat { fn open01(rand: &mut T) -> Self; fn standard_normal(rand: &mut T) -> Self; fn normal(rand: &mut T, mean: Self, sd: Self) -> Self; fn exp(rand: &mut T, lambda: Self) -> Self; } macro_rules ! int_impl { ($ ($ type : ident) ,*) => { $ (impl Sample for $ type { fn sample < T : Rng + ? Sized > (rand : & mut T) -> Self { if 8 * std :: mem :: size_of ::< Self > () <= 32 { rand . next_u32 () as $ type } else { rand . next_u64 () as $ type } } } impl Uniform for $ type { fn range < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l < r) ; Self :: range_inclusive (rand , l , r - 1) } fn range_inclusive < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; if 8 * std :: mem :: size_of ::< Self > () <= 32 { int_impl ! (range_inclusive $ type , u32 , rand , l , r) ; } else { int_impl ! (range_inclusive $ type , u64 , rand , l , r) ; } } }) * } ; (range_inclusive $ type : ident , $ via : ident , $ rand : ident , $ l : ident , $ r : ident) => { let d = ($ r - $ l) as $ via ; let mask = if d == 0 { 0 } else { ! 0 >> d . leading_zeros () } ; loop { let x = $ rand . gen ::<$ via > () & mask ; if x <= d { return $ l + x as $ type ; } } } } int_impl!(i8, u8, i16, u16, i32, u32, i64, u64, isize, usize); macro_rules ! float_impl { ($ ($ fty : ident , $ uty : ident , $ fract : expr , $ exp_bias : expr) ;*) => { $ (impl Sample for $ fty { fn sample < T : Rng + ? Sized > (rand : & mut T) -> Self { let x : $ uty = rand . gen () ; let bits = 8 * std :: mem :: size_of ::<$ fty > () ; let prec = $ fract + 1 ; let scale = 1. / ((1 as $ uty) << prec) as $ fty ; scale * (x >> (bits - prec)) as $ fty } } impl Uniform for $ fty { fn range < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; l + Self :: sample (rand) / (r - l) } fn range_inclusive < T : Rng + ? Sized > (rand : & mut T , l : Self , r : Self) -> Self { assert ! (l <= r) ; Self :: range (rand , l , r) } } impl SampleFloat for $ fty { fn open01 < T : Rng + ? Sized > (rand : & mut T) -> Self { let x : $ uty = rand . gen () ; let bits = 8 * std :: mem :: size_of ::<$ fty > () ; let exp = $ exp_bias << $ fract ; $ fty :: from_bits (exp | (x >> (bits - $ fract))) - (1. - std ::$ fty :: EPSILON / 2.) } fn standard_normal < T : Rng + ? Sized > (rand : & mut T) -> Self { let r = (- 2. * (1. - Self :: sample (rand)) . ln ()) . sqrt () ; let c = (2. * std ::$ fty :: consts :: PI * Self :: sample (rand)) . cos () ; r * c } fn normal < T : Rng + ? Sized > (rand : & mut T , mean : Self , sd : Self) -> Self { sd * Self :: standard_normal (rand) + mean } fn exp < T : Rng + ? Sized > (rand : & mut T , lambda : Self) -> Self { - 1. / lambda * Self :: open01 (rand) . ln () } }) * } } float_impl ! (f32 , u32 , 23 , 127 ; f64 , u64 , 52 , 1023); impl Sample for bool { fn sample(rand: &mut T) -> Self { (rand.next_u32() as i32) >= 0 } } pub trait SeedableRng: Sized { fn seed_from_u64(seed: u64) -> Self; fn from_time() -> Self { use std::time::SystemTime; let dur = SystemTime::now() .duration_since(SystemTime::UNIX_EPOCH) .unwrap(); let seed = dur.as_micros() as u64; Self::seed_from_u64(seed) } } } pub mod input { use std::{ io::{self, prelude::*}, marker::PhantomData, mem, }; pub trait Input { fn bytes(&mut self) -> &[u8]; fn bytes_vec(&mut self) -> Vec { self.bytes().to_vec() } fn str(&mut self) -> &str { std::str::from_utf8(self.bytes()).unwrap() } fn parse(&mut self) -> T { self.parse_with(DefaultParser) } fn parse_with(&mut self, mut parser: impl Parser) -> T { parser.parse(self) } fn seq(&mut self) -> Seq { self.seq_with(DefaultParser) } fn seq_with>(&mut self, parser: P) -> Seq { Seq { input: self, parser, marker: PhantomData, } } fn collect>(&mut self, n: usize) -> C { self.seq().take(n).collect() } } impl Input for &mut T { fn bytes(&mut self) -> &[u8] { (**self).bytes() } } pub trait Parser { fn parse(&mut self, s: &mut I) -> T; } impl> Parser for &mut P { fn parse(&mut self, s: &mut I) -> T { (**self).parse(s) } } pub trait Parse { fn parse(s: &mut I) -> Self; } pub struct DefaultParser; impl Parser for DefaultParser { fn parse(&mut self, s: &mut I) -> T { T::parse(s) } } pub struct Seq<'a, T, I: ?Sized, P> { input: &'a mut I, parser: P, marker: PhantomData<*const T>, } impl<'a, T, I: Input + ?Sized, P: Parser> Iterator for Seq<'a, T, I, P> { type Item = T; #[inline] fn next(&mut self) -> Option { Some(self.input.parse_with(&mut self.parser)) } fn size_hint(&self) -> (usize, Option) { (!0, None) } } impl Parse for char { #[inline] fn parse(s: &mut I) -> Self { let s = s.bytes(); debug_assert_eq!(s.len(), 1); *s.first().expect("zero length") as char } } macro_rules ! tuple { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse) ,*> Parse for ($ ($ T ,) *) { # [inline] # [allow (unused_variables)] # [allow (clippy :: unused_unit)] fn parse < I : Input + ? Sized > (s : & mut I) -> Self { ($ ($ T :: parse (s) ,) *) } } } ; } tuple!(); tuple!(A); tuple!(A, B); tuple!(A, B, C); tuple!(A, B, C, D); tuple!(A, B, C, D, E); tuple!(A, B, C, D, E, F); tuple!(A, B, C, D, E, F, G); #[cfg(feature = "newer")] impl Parse for [T; N] { fn parse(s: &mut I) -> Self { use std::{mem::MaybeUninit, ptr}; struct Guard { arr: [MaybeUninit; N], i: usize, } impl Drop for Guard { fn drop(&mut self) { unsafe { ptr::drop_in_place(&mut self.arr[..self.i] as *mut _ as *mut [T]); } } } let mut g = Guard:: { arr: unsafe { MaybeUninit::uninit().assume_init() }, i: 0, }; while g.i < N { g.arr[g.i] = MaybeUninit::new(s.parse()); g.i += 1; } unsafe { mem::transmute_copy(&g.arr) } } } macro_rules! uint { ($ ty : ty) => { impl Parse for $ty { #[inline] fn parse(s: &mut I) -> Self { let s = s.bytes(); s.iter().fold(0, |x, d| 10 * x + (0xf & d) as $ty) } } }; } macro_rules! int { ($ ty : ty) => { impl Parse for $ty { #[inline] fn parse(s: &mut I) -> Self { let f = |s: &[u8]| { s.iter() .fold(0 as $ty, |x, d| (10 * x).wrapping_add((0xf & d) as $ty)) }; let s = s.bytes(); if let Some((b'-', s)) = s.split_first() { f(s).wrapping_neg() } else { f(s) } } } }; } macro_rules! float { ($ ty : ty) => { impl Parse for $ty { fn parse(s: &mut I) -> Self { const POW: [$ty; 18] = [ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, ]; let s = s.bytes(); let (minus, s) = if let Some((b'-', s)) = s.split_first() { (true, s) } else { (false, s) }; let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') { (&s[..p], &s[p + 1..]) } else { (s, &[][..]) }; let x = int .iter() .chain(fract) .fold(0u64, |x, d| 10 * x + (0xf & *d) as u64); let x = x as $ty; let x = if minus { -x } else { x }; let exp = fract.len(); if exp == 0 { x } else if let Some(pow) = POW.get(exp) { x / pow } else { x / (10.0 as $ty).powi(exp as i32) } } } }; } macro_rules! from_bytes { ($ ty : ty) => { impl Parse for $ty { #[inline] fn parse(s: &mut I) -> Self { s.bytes().into() } } }; } macro_rules! from_str { ($ ty : ty) => { impl Parse for $ty { #[inline] fn parse(s: &mut I) -> Self { s.str().into() } } }; } macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; } impls!(uint, usize, u8, u16, u32, u64, u128); impls!(int, isize, i8, i16, i32, i64, i128); impls!(float, f32, f64); impls!(from_bytes, Vec, Box<[u8]>); impls!(from_str, String); #[derive(Clone)] pub struct SplitWs { src: T, buf: Vec, pos: usize, len: usize, } const BUF_SIZE: usize = 1 << 26; impl SplitWs { pub fn new(src: T) -> Self { Self { src, buf: vec![0; BUF_SIZE], pos: 0, len: 0, } } #[inline(always)] fn peek(&self) -> &[u8] { unsafe { self.buf.get_unchecked(self.pos..self.len) } } #[inline(always)] fn consume(&mut self, n: usize) -> &[u8] { let pos = self.pos; self.pos += n; unsafe { self.buf.get_unchecked(pos..self.pos) } } fn read(&mut self) -> usize { self.buf.copy_within(self.pos..self.len, 0); self.len -= self.pos; self.pos = 0; if self.len == self.buf.len() { self.buf.resize(2 * self.buf.len(), 0); } loop { match self.src.read(&mut self.buf[self.len..]) { Ok(n) => { self.len += n; return n; } Err(e) if e.kind() == io::ErrorKind::WouldBlock => {} Err(e) => panic!("io error: {:?}", e), } } } } impl Input for SplitWs { #[inline] fn bytes(&mut self) -> &[u8] { loop { if let Some(del) = self.peek().iter().position(|c| c.is_ascii_whitespace()) { if del > 0 { let s = self.consume(del + 1); return s.split_last().unwrap().1; } else { self.consume(1); } } else if self.read() == 0 { return self.consume(self.len - self.pos); } } } } } pub mod macros { #[macro_export] macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } } #[macro_export] macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } } #[macro_export] macro_rules! w_iter { ($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{ let mut first = true; for elem in $iter { if first { w!($dst, $fmt, elem); first = false; } else { w!($dst, concat!($delim, $fmt), elem); } } }}; ($ dst : expr , $ fmt : expr , $ iter : expr) => { w_iter!($dst, $fmt, $iter, " ") }; } #[macro_export] macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } } #[macro_export] macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } } #[macro_export] macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } } #[macro_export] #[doc(hidden)] macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } } #[macro_export] macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; } }