import Ġjava . util .*; Ċ import Ġjava . util . concurrent .* Ċ import Ġjava . util . function .* Ċ import Ġjava . util . regex .* Ċ import Ġjava . util . stream .* Ċ import Ġkotlin . collections .* Ċ import Ġkotlin . comp arisons .* Ċ import Ġkotlin . io .* Ċ import Ġkotlin . jvm .* Ċ import Ġkotlin . jvm . functions .* Ċ import Ġkotlin . jvm . internal .* Ċ import Ġkotlin . ranges .* Ċ import Ġkotlin . sequences .* Ċ import Ġkotlin . text .* ĊĊ Ċ class ĠComp ressed Row ( val Ġnodes : ĠList < Node >) Ġ{ ĊĠ Ġdata Ġclass ĠNode ( val Ġstart : ĠInt , Ġval Ġend : ĠInt , Ġval Ġvalue : ĠChar ) Ġ{ ĊĠĠĠ Ġval Ġsize : ĠInt Ġ= Ġend Ġ- Ġstart ĊĠ Ġ} ĊĊĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠ Ġfun Ġfrom String ( row String : ĠString ): ĠComp ressed Row Ġ{ ĊĠĠĠĠĠ Ġval Ġnodes Ġ= Ġmutable ListOf < Node >() ĊĠĠĠĠĠ Ġvar Ġlast Char Ġ= Ġrow String [ 0 ] ĊĠĠĠĠĠ Ġvar Ġlast Start Ġ= Ġ 0 ĊĊĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġrow String . length ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġchar Ġ= Ġrow String [ i ] ĊĠĠĠĠĠĠĠ Ġif Ġ( char Ġ== Ġlast Char ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġnodes . add ( Node ( last Start , Ġi , Ġlast Char )) ĊĠĠĠĠĠĠĠ Ġlast Start Ġ= Ġi ĊĠĠĠĠĠĠĠ Ġlast Char Ġ= Ġchar ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġnodes . add ( Node ( last Start , Ġrow String . length , Ġlast Char )) ĊĊĠĠĠĠĠ Ġreturn ĠComp ressed Row ( nodes ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfrom Array ( grid : ĠArray < String >): ĠList < Compressed Row > Ġ{ ĊĠĠĠĠĠ Ġreturn Ġgrid . map Ġ{ Ġrow Ġ-> Ġfrom String ( row ) Ġ} ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠ Ġreturn Ġnodes . flatMap Ġ{ Ġnode Ġ-> ĊĠĠĠĠĠ Ġ( 1 .. node . end Ġ- Ġnode . start ). map Ġ{ Ġnode . value Ġ} ĊĠĠĠ Ġ}. join ToString ("") ĊĠ Ġ} ĊĊĠ Ġfun Ġstarting Indices ( pattern : ĠComp ressed Row ): ĠSet < Int > Ġ{ ĊĠĠĠ Ġval Ġindices Ġ= Ġmutable Set Of < Int >() ĊĠĠĠ Ġif Ġ( pattern . nodes . size Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠ Ġval Ġpattern Node Ġ= Ġpattern . nodes [ 0 ] ĊĠĠĠĠĠ Ġfor Ġ( grid Node Ġin Ġnodes ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( grid Node . value Ġ== Ġpattern Node . value Ġ&& Ġgrid Node . size Ġ>= Ġpattern Node . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġgrid Node . start .. grid Node . end Ġ- Ġpattern Node . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindices . add ( i ) ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġreturn Ġindices ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġloop @ Ġfor Ġ( starting Index Ġin Ġ 0 .. nodes . size Ġ- Ġpattern . nodes . size ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġpattern . nodes . size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpattern Node Ġ= Ġpattern . nodes [ i ] ĊĠĠĠĠĠĠĠ Ġval Ġgrid Node Ġ= Ġnodes [ starting Index Ġ+ Ġi ] ĊĠĠĠĠĠĠĠ Ġif Ġ( pattern Node . value Ġ!= Ġgrid Node . value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// ĠIt 's Ġnot Ġthe Ġsame Ġsequence Ġof Ġchars , Ġso Ġit Ġcannot Ġmatch ĊĠĠĠĠĠĠĠĠĠ Ġcontinue @ loop ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( pattern Node . size Ġ> Ġgrid Node . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// ĠPattern Ġhas Ġmore Ġchars Ġin Ġthe Ġsequence ĊĠĠĠĠĠĠĠĠĠ Ġcontinue @ loop ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( i Ġ!= Ġ 0 Ġ&& Ġi Ġ!= Ġpattern . nodes . size Ġ- Ġ 1 Ġ&& Ġpattern Node . size Ġ!= Ġgrid Node . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġ// ĠUnless Ġit 's Ġthe Ġprefix / suffix Ġwe 're Ġmatching , Ġthe Ġ# Ġof Ġchars Ġneed Ġto Ġmatch ĊĠĠĠĠĠĠĠĠĠ Ġcontinue @ loop ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠ Ġindices . add ( nodes [ starting Index ]. end Ġ- Ġpattern . nodes [ 0 ]. size ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġindices ĊĠ Ġ} Ċ } Ċ Ċ // ĠComplete Ġthe Ġgrid Search Ġfunction Ġbelow . Ċ fun Ġgrid Search ( g : ĠArray < String >, Ġp : ĠArray < String >): ĠString Ġ{ ĊĠ Ġval Ġgrid Ġ= ĠComp ressed Row . from Array ( g ) ĊĠ Ġval Ġpattern Ġ= ĠComp ressed Row . from Array ( p ) ĊĊĠ Ġval Ġstarting Indices Ġ= ĠArray < Set < Int >>( p . size ) Ġ{ Ġempty Set < Int >() Ġ} ĊĊĠ Ġfor Ġ( grid Start RowIndex Ġin Ġ 0 .. g . size Ġ- Ġp . size ) Ġ{ ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġp . size ) Ġ{ ĊĠĠĠĠĠ Ġval Ġgrid Row Ġ= Ġgrid [ grid Start RowIndex Ġ+ Ġi ] ĊĠĠĠĠĠ Ġval Ġpattern Row Ġ= Ġpattern [ i ] ĊĠĠĠĠĠ Ġstarting Indices [ i ] Ġ= Ġgrid Row . starting Indices ( pattern Row ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġis Match Ġ= Ġstarting Indices [ 0 ]. any Ġ{ Ġindex Ġ-> ĊĠĠĠĠĠ Ġstarting Indices . all Ġ{ Ġs Ġ-> Ġs . contains ( index ) Ġ} ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġif Ġ( is Match ) Ġ{ ĊĠĠĠĠĠ Ġreturn Ġ" YES " ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġreturn Ġ" NO " Ċ } Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠ Ġval Ġscan Ġ= ĠScanner ( System .` in `) ĊĊĠ Ġval Ġt Ġ= Ġscan . nextLine (). trim (). toInt () ĊĊĠ Ġfor Ġ( t Itr Ġin Ġ 1 .. t ) Ġ{ ĊĠĠĠ Ġval ĠRC Ġ= Ġscan . nextLine (). split (" Ġ") ĊĊĠĠĠ Ġval ĠR Ġ= ĠRC [ 0 ]. trim (). toInt () ĊĊĠĠĠ Ġval ĠC Ġ= ĠRC [ 1 ]. trim (). toInt () ĊĊĠĠĠ Ġval ĠG Ġ= ĠArray < String >( R , Ġ{ Ġ"" Ġ}) ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil ĠR ) Ġ{ ĊĠĠĠĠĠ Ġval ĠG Item Ġ= Ġscan . nextLine () ĊĠĠĠĠĠ ĠG [ i ] Ġ= ĠG Item ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġrc Ġ= Ġscan . nextLine (). split (" Ġ") ĊĊĠĠĠ Ġval Ġr Ġ= Ġrc [ 0 ]. trim (). toInt () ĊĊĠĠĠ Ġval Ġc Ġ= Ġrc [ 1 ]. trim (). toInt () ĊĊĠĠĠ Ġval ĠP Ġ= ĠArray < String >( r , Ġ{ Ġ"" Ġ}) ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġr ) Ġ{ ĊĠĠĠĠĠ Ġval ĠP Item Ġ= Ġscan . nextLine () ĊĠĠĠĠĠ ĠP [ i ] Ġ= ĠP Item ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġresult Ġ= Ġgrid Search ( G , ĠP ) ĊĊĠĠĠ Ġprintln ( result ) ĊĠ Ġ} Ċ } Ċ Ċ main ( array Of ()) Ċ