import Control.Monad
import GHC.Base (build)
 
data Tree a
    = Nil
    | Branch !a (Tree a) (Tree a)
    deriving (Show, Eq)
 
foldrNotEach :: (Tree Bool -> b -> b) -> b -> Tree Bool -> b 
foldrNotEach f init (Branch x l r) =
  Branch (not $! x) l r `f` 
    foldrNotEach 
      (\l' -> f (Branch x l' r))
      (foldrNotEach (\r' -> f (Branch x l r')) init r)
      l
foldrNotEach _ init Nil = init
{-# SPECIALIZE foldrNotEach :: (Tree Bool -> [Tree Bool] -> [Tree Bool]) -> [Tree Bool] -> Tree Bool -> [Tree Bool] #-}
 
notEach :: Tree Bool -> [Tree Bool]
notEach t = build (\c n -> foldrNotEach c n t)
{-# INLINE[0] notEach #-}
 
procreateL :: Int -> Tree Bool
procreateL 0 = Nil
procreateL n = Branch (n `rem` 2 == 0) (procreateL (n - 1)) (procreateL (n `div` 2))
 
procreateR :: Int -> Tree Bool
procreateR 0 = Nil
procreateR n = Branch (n `rem` 2 == 0) (procreateR (n `div` 2)) (procreateR (n - 1))
 
test :: IO ()
test = do
    guard $ notEach (procreateL 3) == [Branch True (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch False (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch True Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch True Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch True Nil Nil)]
    guard $ notEach (procreateR 3) == [Branch True (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch True Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch False (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch True Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch True Nil Nil))]
    guard $ length (notEach $ procreateL 150) == 1564307
    guard $ length (notEach $ procreateR 150) == 1564307
 
main = test

aW1wb3J0IENvbnRyb2wuTW9uYWQKaW1wb3J0IEdIQy5CYXNlIChidWlsZCkKCmRhdGEgVHJlZSBhCiAgICA9IE5pbAogICAgfCBCcmFuY2ggIWEgKFRyZWUgYSkgKFRyZWUgYSkKICAgIGRlcml2aW5nIChTaG93LCBFcSkKCmZvbGRyTm90RWFjaCA6OiAoVHJlZSBCb29sIC0+IGIgLT4gYikgLT4gYiAtPiBUcmVlIEJvb2wgLT4gYiAKZm9sZHJOb3RFYWNoIGYgaW5pdCAoQnJhbmNoIHggbCByKSA9CiAgQnJhbmNoIChub3QgJCEgeCkgbCByIGBmYCAKICAgIGZvbGRyTm90RWFjaCAKICAgICAgKFxsJyAtPiBmIChCcmFuY2ggeCBsJyByKSkKICAgICAgKGZvbGRyTm90RWFjaCAoXHInIC0+IGYgKEJyYW5jaCB4IGwgcicpKSBpbml0IHIpCiAgICAgIGwKZm9sZHJOb3RFYWNoIF8gaW5pdCBOaWwgPSBpbml0CnstIyBTUEVDSUFMSVpFIGZvbGRyTm90RWFjaCA6OiAoVHJlZSBCb29sIC0+IFtUcmVlIEJvb2xdIC0+IFtUcmVlIEJvb2xdKSAtPiBbVHJlZSBCb29sXSAtPiBUcmVlIEJvb2wgLT4gW1RyZWUgQm9vbF0gIy19Cgpub3RFYWNoIDo6IFRyZWUgQm9vbCAtPiBbVHJlZSBCb29sXQpub3RFYWNoIHQgPSBidWlsZCAoXGMgbiAtPiBmb2xkck5vdEVhY2ggYyBuIHQpCnstIyBJTkxJTkVbMF0gbm90RWFjaCAjLX0KCnByb2NyZWF0ZUwgOjogSW50IC0+IFRyZWUgQm9vbApwcm9jcmVhdGVMIDAgPSBOaWwKcHJvY3JlYXRlTCBuID0gQnJhbmNoIChuIGByZW1gIDIgPT0gMCkgKHByb2NyZWF0ZUwgKG4gLSAxKSkgKHByb2NyZWF0ZUwgKG4gYGRpdmAgMikpCgpwcm9jcmVhdGVSIDo6IEludCAtPiBUcmVlIEJvb2wKcHJvY3JlYXRlUiAwID0gTmlsCnByb2NyZWF0ZVIgbiA9IEJyYW5jaCAobiBgcmVtYCAyID09IDApIChwcm9jcmVhdGVSIChuIGBkaXZgIDIpKSAocHJvY3JlYXRlUiAobiAtIDEpKQoKdGVzdCA6OiBJTyAoKQp0ZXN0ID0gZG8KICAgIGd1YXJkICQgbm90RWFjaCAocHJvY3JlYXRlTCAzKSA9PSBbQnJhbmNoIFRydWUgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSxCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksQnJhbmNoIEZhbHNlIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIFRydWUgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSxCcmFuY2ggRmFsc2UgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIE5pbCBOaWwpKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpLEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSAoQnJhbmNoIFRydWUgTmlsIE5pbCldCiAgICBndWFyZCAkIG5vdEVhY2ggKHByb2NyZWF0ZVIgMykgPT0gW0JyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksQnJhbmNoIEZhbHNlIChCcmFuY2ggVHJ1ZSBOaWwgTmlsKSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSxCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIChCcmFuY2ggVHJ1ZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSxCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIFRydWUgTmlsIE5pbCkpXQogICAgZ3VhcmQgJCBsZW5ndGggKG5vdEVhY2ggJCBwcm9jcmVhdGVMIDE1MCkgPT0gMTU2NDMwNwogICAgZ3VhcmQgJCBsZW5ndGggKG5vdEVhY2ggJCBwcm9jcmVhdGVSIDE1MCkgPT0gMTU2NDMwNwogICAgCm1haW4gPSB0ZXN0