pub struct Writer { writer: BufWriter, } impl Writer { pub fn new(write: W) -> Self { Self { writer: BufWriter::new(write), } } pub fn ln(&mut self, s: S) { writeln!(self.writer, "{}", s).expect("Failed to write.") } pub fn out(&mut self, s: S) { write!(self.writer, "{}", s).expect("Failed to write.") } pub fn join(&mut self, v: &[S], separator: &str) { v.iter().fold("", |sep, arg| { write!(self.writer, "{}{}", sep, arg).expect("Failed to write."); separator }); writeln!(self.writer).expect("Failed to write."); } pub fn bits(&mut self, i: i64, len: usize) { (0..len).for_each(|b| write!(self.writer, "{}", i >> b & 1).expect("Failed to write.")); writeln!(self.writer).expect("Failed to write.") } pub fn flush(&mut self) { let _ = self.writer.flush(); } } pub struct Reader { init: F, buf: VecDeque, } impl R> Iterator for Reader { type Item = String; fn next(&mut self) -> Option { if self.buf.is_empty() { let mut reader = (self.init)(); let mut l = String::new(); reader.read_line(&mut l).unwrap(); self.buf .append(&mut l.split_whitespace().map(ToString::to_string).collect()); } self.buf.pop_front() } } impl R> Reader { pub fn new(init: F) -> Self { let buf = VecDeque::new(); Reader { init, buf } } pub fn v(&mut self) -> T { let s = self.next().expect("Insufficient input."); s.parse().ok().expect("Failed to parse.") } pub fn v2(&mut self) -> (T1, T2) { (self.v(), self.v()) } pub fn v3(&mut self) -> (T1, T2, T3) { (self.v(), self.v(), self.v()) } pub fn v4(&mut self) -> (T1, T2, T3, T4) { (self.v(), self.v(), self.v(), self.v()) } pub fn v5(&mut self) -> (T1, T2, T3, T4, T5) { (self.v(), self.v(), self.v(), self.v(), self.v()) } pub fn vec(&mut self, length: usize) -> Vec { (0..length).map(|_| self.v()).collect() } pub fn vec2(&mut self, length: usize) -> Vec<(T1, T2)> { (0..length).map(|_| self.v2()).collect() } pub fn vec3(&mut self, length: usize) -> Vec<(T1, T2, T3)> { (0..length).map(|_| self.v3()).collect() } pub fn vec4(&mut self, length: usize) -> Vec<(T1, T2, T3, T4)> { (0..length).map(|_| self.v4()).collect() } pub fn chars(&mut self) -> Vec { self.v::().chars().collect() } fn split(&mut self, zero: u8) -> Vec { self.v::() .chars() .map(|c| (c as u8 - zero) as usize) .collect() } pub fn digits(&mut self) -> Vec { self.split(b'0') } pub fn lowercase(&mut self) -> Vec { self.split(b'a') } pub fn uppercase(&mut self) -> Vec { self.split(b'A') } pub fn char_map(&mut self, h: usize) -> Vec> { (0..h).map(|_| self.chars()).collect() } pub fn bool_map(&mut self, h: usize, ng: char) -> Vec> { self.char_map(h) .iter() .map(|v| v.iter().map(|&c| c != ng).collect()) .collect() } pub fn matrix(&mut self, h: usize, w: usize) -> Vec> { (0..h).map(|_| self.vec(w)).collect() } } pub fn to_lr>(range: &R, length: T) -> (T, T) where T: Copy + One + Zero + Add + PartialOrd, { use Bound::{Excluded, Included, Unbounded}; let l = match range.start_bound() { Unbounded => T::zero(), Included(&s) => s, Excluded(&s) => s + T::one(), }; let r = match range.end_bound() { Unbounded => length, Included(&e) => e + T::one(), Excluded(&e) => e, }; assert!(l <= r && r <= length); (l, r) } pub use std::{ cmp::{max, min, Ordering, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, convert::Infallible, convert::{TryFrom, TryInto}, fmt::{Debug, Display, Formatter}, io::{stdin, stdout, BufRead, BufWriter, Read, Write}, iter::{repeat, Product, Sum}, marker::PhantomData, mem::swap, ops::{ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Bound, Deref, DerefMut, Div, DivAssign, Index, IndexMut, Mul, MulAssign, Neg, Not, Range, RangeBounds, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign, }, str::{from_utf8, FromStr as FS}, }; #[allow(unused_macros)] macro_rules ! chmin {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_min = min ! ($ ($ cmps ) ,+ ) ; if $ base > cmp_min {$ base = cmp_min ; true } else {false } } } ; } #[allow(unused_macros)] macro_rules ! min {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ b } else {$ a } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = min ! ($ ($ rest ) ,+ ) ; if $ a > b {b } else {$ a } } } ; } #[allow(unused_macros)] macro_rules ! chmax {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_max = max ! ($ ($ cmps ) ,+ ) ; if $ base < cmp_max {$ base = cmp_max ; true } else {false } } } ; } #[allow(unused_macros)] macro_rules ! max {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ a } else {$ b } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = max ! ($ ($ rest ) ,+ ) ; if $ a > b {$ a } else {b } } } ; } pub trait Magma { type M: Clone + PartialEq + Debug; fn op(x: &Self::M, y: &Self::M) -> Self::M; } pub trait Associative {} pub trait Unital: Magma { fn unit() -> Self::M; } pub trait Commutative: Magma {} pub trait Invertible: Magma { fn inv(x: &Self::M) -> Self::M; } pub trait Idempotent: Magma {} pub trait SemiGroup: Magma + Associative {} pub trait Monoid: Magma + Associative + Unital { fn pow(&self, x: Self::M, mut n: usize) -> Self::M { let mut res = Self::unit(); let mut base = x; while n > 0 { if n & 1 == 1 { res = Self::op(&res, &base); } base = Self::op(&base, &base); n >>= 1; } res } } impl Monoid for M {} pub trait CommutativeMonoid: Magma + Associative + Unital + Commutative {} impl CommutativeMonoid for M {} pub trait Group: Magma + Associative + Unital + Invertible {} impl Group for M {} pub trait AbelianGroup: Magma + Associative + Unital + Commutative + Invertible {} impl AbelianGroup for M {} pub trait Band: Magma + Associative + Idempotent {} impl Band for M {} pub trait MapMonoid { type Mono: Monoid; type Func: Monoid; fn op( &self, x: &::M, y: &::M, ) -> ::M { Self::Mono::op(x, y) } fn unit() -> ::M { Self::Mono::unit() } fn apply( &self, f: &::M, value: &::M, ) -> ::M; fn identity_map() -> ::M { Self::Func::unit() } fn compose( &self, f: &::M, g: &::M, ) -> ::M { Self::Func::op(f, g) } } pub trait Zero { fn zero() -> Self; } pub trait One { fn one() -> Self; } pub trait BoundedBelow { fn min_value() -> Self; } pub trait BoundedAbove { fn max_value() -> Self; } # [rustfmt :: skip ] pub trait Integral : 'static + Send + Sync + Copy + Ord + Display + Debug + Add < Output = Self > + Sub < Output = Self > + Mul < Output = Self > + Div < Output = Self > + Rem < Output = Self > + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + Sum + Product + BitOr < Output = Self > + BitAnd < Output = Self > + BitXor < Output = Self > + Not < Output = Self > + Shl < Output = Self > + Shr < Output = Self > + BitOrAssign + BitAndAssign + BitXorAssign + ShlAssign + ShrAssign + Zero + One + BoundedBelow + BoundedAbove {} macro_rules ! impl_integral {($ ($ ty : ty ) ,* ) => {$ (impl Zero for $ ty {fn zero () -> Self {0 } } impl One for $ ty {fn one () -> Self {1 } } impl BoundedBelow for $ ty {fn min_value () -> Self {Self :: min_value () } } impl BoundedAbove for $ ty {fn max_value () -> Self {Self :: max_value () } } impl Integral for $ ty {} ) * } ; } impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize); pub fn main() { let stdin = stdin(); let stdout = stdout(); solve(Reader::new(|| stdin.lock()), Writer::new(stdout.lock())); } pub trait SliceBounds { type Item: Ord; fn lower_bound(&self, k: &Self::Item) -> usize; fn upper_bound(&self, k: &Self::Item) -> usize; } pub trait SliceBoundsBy { type Item; fn lower_bound_by Ordering>(&self, f: F) -> usize; fn upper_bound_by Ordering>(&self, f: F) -> usize; } pub trait SliceBoundsByKey { type Item; fn lower_bound_by_key K>(&self, k: &K, f: F) -> usize; fn upper_bound_by_key K>(&self, k: &K, f: F) -> usize; } impl SliceBounds for [T] { type Item = T; fn lower_bound(&self, k: &T) -> usize { self.lower_bound_by(|p| p.cmp(k)) } fn upper_bound(&self, k: &T) -> usize { self.upper_bound_by(|p| p.cmp(k)) } } impl SliceBoundsBy for [T] { type Item = T; fn lower_bound_by Ordering>(&self, mut f: F) -> usize { self.binary_search_by(|p| f(p).then(Ordering::Greater)) .unwrap_err() } fn upper_bound_by Ordering>(&self, mut f: F) -> usize { self.binary_search_by(|p| f(p).then(Ordering::Less)) .unwrap_err() } } impl SliceBoundsByKey for [T] { type Item = T; fn lower_bound_by_key K>(&self, k: &K, mut f: F) -> usize { self.lower_bound_by(|p| f(p).cmp(k)) } fn upper_bound_by_key K>(&self, k: &K, mut f: F) -> usize { self.upper_bound_by(|p| f(p).cmp(k)) } } pub fn solve R>(mut reader: Reader, mut writer: Writer) { let k: usize = reader.v(); let n: usize = reader.v(); let primes = primes(n); let mut v = Vec::new(); for p in primes { if p >= k { v.push(p); } } let mut pos = vec![Vec::new(); 10]; for i in 0..v.len() { let mut p = v[i]; while p > 9 { let d = int_to_digits(p); p = d.iter().fold(0, |x, a| x + a); } pos[p].push(i); } let mut max_len = 0; let mut ans = 0; for i in (0..v.len()).rev() { let mut lim = v.len(); for k in 1..10 { let next = pos[k].lower_bound(&i); if next < pos[k].len() { let limit = pos[k].upper_bound(&pos[k][next]); if limit < pos[k].len() { chmin!(lim, pos[k][limit]); } } } if chmax!(max_len, lim - i) { ans = v[i]; } } writer.ln(ans); } fn int_to_digits(mut n: usize) -> Vec { let mut ret = Vec::new(); if n == 0 { ret.push(0) } while n > 0 { ret.push(n % 10); n /= 10; } ret.reverse(); ret } pub fn primes(m: usize) -> Vec { if m < 2 { return Vec::new(); } if m == 2 { return vec![2]; } let mut b = vec![false; m + 1]; let mut ret = vec![2, 3]; let mut i = 5; let mut f = 4; while i <= m { if !b[i] { ret.push(i); for j in i..m / i + 1 { b[i * j] = true; } } f = 6 - f; i += f; } ret }