{-# 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