import Control.Monad
 
data Tree a
  = Nil
  | Branch a (Tree a) (Tree a)
  deriving (Show, Eq)
 
notEach :: Tree Bool -> [Tree Bool]
notEach t = go t id []
  where
    go :: Tree Bool -> (Tree Bool -> Tree Bool) -> [Tree Bool] -> [Tree Bool]
    go Nil repack acc = acc
    go (Branch x l r) repack acc =
      let acc1 = go r (\r' -> repack $ Branch x l r') acc
          acc2 = go l (\l' -> repack $ Branch x l' r) acc1
          acc3 = (repack (Branch (not x) l r)) : acc2
       in acc3
 
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
 

aW1wb3J0IENvbnRyb2wuTW9uYWQKCmRhdGEgVHJlZSBhCiAgPSBOaWwKICB8IEJyYW5jaCBhIChUcmVlIGEpIChUcmVlIGEpCiAgZGVyaXZpbmcgKFNob3csIEVxKQoKbm90RWFjaCA6OiBUcmVlIEJvb2wgLT4gW1RyZWUgQm9vbF0Kbm90RWFjaCB0ID0gZ28gdCBpZCBbXQogIHdoZXJlCiAgICBnbyA6OiBUcmVlIEJvb2wgLT4gKFRyZWUgQm9vbCAtPiBUcmVlIEJvb2wpIC0+IFtUcmVlIEJvb2xdIC0+IFtUcmVlIEJvb2xdCiAgICBnbyBOaWwgcmVwYWNrIGFjYyA9IGFjYwogICAgZ28gKEJyYW5jaCB4IGwgcikgcmVwYWNrIGFjYyA9CiAgICAgIGxldCBhY2MxID0gZ28gciAoXHInIC0+IHJlcGFjayAkIEJyYW5jaCB4IGwgcicpIGFjYwogICAgICAgICAgYWNjMiA9IGdvIGwgKFxsJyAtPiByZXBhY2sgJCBCcmFuY2ggeCBsJyByKSBhY2MxCiAgICAgICAgICBhY2MzID0gKHJlcGFjayAoQnJhbmNoIChub3QgeCkgbCByKSkgOiBhY2MyCiAgICAgICBpbiBhY2MzCgpwcm9jcmVhdGVMIDo6IEludCAtPiBUcmVlIEJvb2wKcHJvY3JlYXRlTCAwID0gTmlsCnByb2NyZWF0ZUwgbiA9IEJyYW5jaCAobiBgcmVtYCAyID09IDApIChwcm9jcmVhdGVMIChuIC0gMSkpIChwcm9jcmVhdGVMIChuIGBkaXZgIDIpKQoKcHJvY3JlYXRlUiA6OiBJbnQgLT4gVHJlZSBCb29sCnByb2NyZWF0ZVIgMCA9IE5pbApwcm9jcmVhdGVSIG4gPSBCcmFuY2ggKG4gYHJlbWAgMiA9PSAwKSAocHJvY3JlYXRlUiAobiBgZGl2YCAyKSkgKHByb2NyZWF0ZVIgKG4gLSAxKSkKCnRlc3QgOjogSU8gKCkKdGVzdCA9IGRvCiAgZ3VhcmQgJCBub3RFYWNoIChwcm9jcmVhdGVMIDMpID09IFtCcmFuY2ggVHJ1ZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpLCBCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksIEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBUcnVlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksIEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIFRydWUgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksIEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSAoQnJhbmNoIFRydWUgTmlsIE5pbCldCiAgZ3VhcmQgJCBub3RFYWNoIChwcm9jcmVhdGVSIDMpID09IFtCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpLCBCcmFuY2ggRmFsc2UgKEJyYW5jaCBUcnVlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpLCBCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksIEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIFRydWUgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksIEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSBOaWwgTmlsKSldCiAgZ3VhcmQgJCBsZW5ndGggKG5vdEVhY2ggJCBwcm9jcmVhdGVMIDE1MCkgPT0gMTU2NDMwNwogIGd1YXJkICQgbGVuZ3RoIChub3RFYWNoICQgcHJvY3JlYXRlUiAxNTApID09IDE1NjQzMDcKCm1haW4gPSB0ZXN0Cg==