import System.Environment
import Data.List

main :: IO ()
main = do
  args <- getArgs
  contents <- getContents
  putStr.unlines.applyBH args $ lines contents

applyBH :: [String] -> [String] -> [String]
applyBH (tm:dt:[]) (cnt:r:bodies) =
  let bodiesIn = map (readBody.words) $ take (read cnt) bodies
      bodiesOut = barnesHut (read tm) (read dt) (read r) bodiesIn in
  cnt:r:(map show bodiesOut)
applyBH _ _ = error "Invalid input"

data Body = Body [Double] [Double] Double deriving Show

readBody :: [String] -> Body
readBody (x:y:vx:vy:m:_) = Body [read x,read y] [read vx,read vy] (read m)
readBody _ = error "Invalid input"

barnesHut :: Double -> Double -> Double -> [Body] -> [Body]
barnesHut tm dt r bodies = snd $ until ((<=0).fst) (tick dt r) (tm, bodies)

tick :: Double -> Double -> (Double, [Body]) -> (Double, [Body])
tick dt r (tm, bodies) =
  let tree = makeQT [0,0] r pos summary bodies in
  (tm-dt, map (updateBody tree dt) bodies)

updateBody :: (QT Body) -> Double -> Body -> Body
updateBody tree dt (Body p v m) =
  let threshold = 0.5
      sumOk r (Body c _ _) = r/(dist p c) < threshold
      aList = transpose $ visitQT sumOk (calcAcc p) tree
      v' = zipWith (+) v $ map ((dt*).sum) aList
      p' = zipWith (+) p $ map (dt*) v' in
  Body p' v' m

pos :: Body -> [Double]
pos (Body p _ _) = p

summary :: [Body] -> Body
summary bodies =
  let masses = map (\(Body _ _ m)->m) bodies
      totalM = sum masses
      wPos = transpose $ zipWith (\m->map (m*)) masses $ map pos bodies in
  Body (map ((/totalM).sum) wPos) [0,0] totalM

dist :: [Double] -> [Double] -> Double
dist v v' = sqrt.sum.map (**2) $ zipWith (-) v v'

calcAcc :: [Double] -> Body -> [Double]
calcAcc p (Body p' _ m') =
  let constG = 0.0000000000667
      accel = constG * m' / (dist p p' ** 3) in
  if p==p' then [0,0] else map (accel*) $ zipWith (-) p' p

data QT a = QT Double a [QT a]

makeQT :: [Double] -> Double -> (a->[Double]) -> ([a]->a) -> [a] -> (QT a)
makeQT _ _ _ _ [] = error "No data to make tree"
makeQT _ r _ _ [x] = QT r x []
makeQT c r toXY f nodes =
  let quad b = map (\x->if x then r/2 else -r/2) $ zipWith (<) c (toXY b)
      quads = groupBy (\a b->quad a==(quad b)) nodes
      newC n = zipWith (+) c ((quad.head) n) in
  QT r (f nodes) $ map (\n->makeQT (newC n) (r/2) toXY f n) quads

visitQT :: (Double->a->Bool) -> (a->b) -> (QT a) -> [b]
visitQT _ dF (QT _ d []) = [dF d]
visitQT sF dF (QT r s children) =
  if sF r s then [dF s] else concatMap (visitQT sF dF) children