{-# OPTIONS_GHC -O2 -fno-cse #-}
primesTMWE = ([2,3,5,7 :: Int]++) . _Y $ (11:) .
                   gapsW 13 (tail wheel) . joinT3 . rollW 11 wheel
 
_Y g = g (_Y g)                     -- telescopic
       -- g xs where xs = g xs      -- two-stage 
 
gapsW k ws@(w:t) cs@(c:u) | k==c  = gapsW (k+w) t u 
                          | True  = k : gapsW (k+w) t cs  
rollW k ws@(w:t) ps@(p:u) | k==p  = scanl (\c d->c+p*d) (p*p) ws 
                                      : rollW (k+w) t u 
                          | True  = rollW (k+w) t ps    
joinT3 ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)    
                                   `union` joinT3 (pairs t)  
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
        4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
 
main = do 
   x <- read `fmap` getLine                --   100k    1mln     2mln     4mln
   mapM_ print                             --  6.8MB   6.8MB    6.8MB    6.8MB     -- !!!!!
         . take 2 . map fst                --  0.13s   2.01s    4.67s    10.71s    -- [Integer], tele, no -O2
         . tail . iterate (splitAt 10.snd) --      n^1.19  n^1.22   n^1.20         -- !!!!
         $ ([], drop (x-10) primesTMWE)    --  0.08s   1.31s    3.18s     7.93s    -- [Int], telescopic
 
pairs (xs:ys:t) = union xs ys : pairs t    --  0.08s   1.41s    3.36s     7.96s    -- [Int], two-stage
union (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : union  xs  (y:ys)
           EQ -> x : union  xs     ys 
           GT -> y : union (x:xs)  ys

ey0jIE9QVElPTlNfR0hDIC1PMiAtZm5vLWNzZSAjLX0KcHJpbWVzVE1XRSA9IChbMiwzLDUsNyA6OiBJbnRdKyspIC4gX1kgJCAoMTE6KSAuCiAgICAgICAgICAgICAgICAgICBnYXBzVyAxMyAodGFpbCB3aGVlbCkgLiBqb2luVDMgLiByb2xsVyAxMSB3aGVlbAoKX1kgZyA9IGcgKF9ZIGcpICAgICAgICAgICAgICAgICAgICAgLS0gdGVsZXNjb3BpYwogICAgICAgLS0gZyB4cyB3aGVyZSB4cyA9IGcgeHMgICAgICAtLSB0d28tc3RhZ2UgCiAKZ2Fwc1cgayB3c0Aodzp0KSBjc0AoYzp1KSB8IGs9PWMgID0gZ2Fwc1cgKGsrdykgdCB1IAogICAgICAgICAgICAgICAgICAgICAgICAgIHwgVHJ1ZSAgPSBrIDogZ2Fwc1cgKGsrdykgdCBjcyAgCnJvbGxXIGsgd3NAKHc6dCkgcHNAKHA6dSkgfCBrPT1wICA9IHNjYW5sIChcYyBkLT5jK3AqZCkgKHAqcCkgd3MgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgOiByb2xsVyAoayt3KSB0IHUgCiAgICAgICAgICAgICAgICAgICAgICAgICAgfCBUcnVlICA9IHJvbGxXIChrK3cpIHQgcHMgICAgCmpvaW5UMyAoKHg6eHMpOiB+KHlzOnpzOnQpKSA9IHggOiB1bmlvbiB4cyAodW5pb24geXMgenMpICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGB1bmlvbmAgam9pblQzIChwYWlycyB0KSAgCndoZWVsID0gMjo0OjI6NDo2OjI6Njo0OjI6NDo2OjY6Mjo2OjQ6Mjo2OjQ6Njo4OjQ6Mjo0OjI6CiAgICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aGVlbAoKbWFpbiA9IGRvIAogICB4IDwtIHJlYWQgYGZtYXBgIGdldExpbmUgICAgICAgICAgICAgICAgLS0gICAxMDBrICAgIDFtbG4gICAgIDJtbG4gICAgIDRtbG4KICAgbWFwTV8gcHJpbnQgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC0tICA2LjhNQiAgIDYuOE1CICAgIDYuOE1CICAgIDYuOE1CICAgICAtLSAhISEhIQogICAgICAgICAuIHRha2UgMiAuIG1hcCBmc3QgICAgICAgICAgICAgICAgLS0gIDAuMTNzICAgMi4wMXMgICAgNC42N3MgICAgMTAuNzFzICAgIC0tIFtJbnRlZ2VyXSwgdGVsZSwgbm8gLU8yCiAgICAgICAgIC4gdGFpbCAuIGl0ZXJhdGUgKHNwbGl0QXQgMTAuc25kKSAtLSAgICAgIG5eMS4xOSAgbl4xLjIyICAgbl4xLjIwICAgICAgICAgLS0gISEhIQogICAgICAgICAkIChbXSwgZHJvcCAoeC0xMCkgcHJpbWVzVE1XRSkgICAgLS0gIDAuMDhzICAgMS4zMXMgICAgMy4xOHMgICAgIDcuOTNzICAgIC0tIFtJbnRdLCB0ZWxlc2NvcGljCgpwYWlycyAoeHM6eXM6dCkgPSB1bmlvbiB4cyB5cyA6IHBhaXJzIHQgICAgLS0gIDAuMDhzICAgMS40MXMgICAgMy4zNnMgICAgIDcuOTZzICAgIC0tIFtJbnRdLCB0d28tc3RhZ2UKdW5pb24gKHg6eHMpICh5OnlzKSA9IGNhc2UgKGNvbXBhcmUgeCB5KSBvZiAKICAgICAgICAgICBMVCAtPiB4IDogdW5pb24gIHhzICAoeTp5cykKICAgICAgICAgICBFUSAtPiB4IDogdW5pb24gIHhzICAgICB5cyAKICAgICAgICAgICBHVCAtPiB5IDogdW5pb24gKHg6eHMpICB5cw==

MTAwMDAw

100000