For the purposes of this challenge, we define a postfix [regex](https://en.wikipedia.org/wiki/Regular_expression) dialect with alphabet `{1, 0}` and the following operations:

* `1` and `0` match themselves literally.
* `_` matches the empty string.
* `!` always fails (i.e. it does not match anything).
* `ab;` matches `a`, followed by `b`.
* `ab|` matches both `a` and `b`.
* `a+` matches one or more instances of `a`.

The regex should always start matching from the start of the string, and stop matching at the end of a string (in other word, it is implicitly wrapped in `^$`).

As an example, the following regex matches any string with an even number of `1`s:

```
0+_|10+_|;10+_|;;+_|;

```

This is equivalent to the regex `0*(10*10*)*`.

The following regex matches any nonempty string of ASCII letters, expressed in binary:

```
110|010|10|10|10|;;;;1010|10|10|;;;10010|;10;|;;|;|;;+

```

This is equivalent to the regex `(1.(0....|1(0...|10(0.|10))))*` (where `.` matches any character.

You can test regexes with [this program](https://tio.run/##fZNRb5swEMff/SluqBKJolbklSRIXZ9atY3UaXupqsjAtaA6GBlnY1K@e3ZnE0IbOkdxzvf/Gd/9HQrZvKNSh0O5rbWxcKMra7S6uq5rVWbSlr9RiFxaCU8trOBWQDf2sB7EjzulBstfuswHyxtpeftTO8hdq/PcgzbIGVFL0yDEMfywpqze4DLhtM@uoECZwxW8apUrcMkQnl/gT4EG3dO6nGkbCOchlx1TfCZFLK1HpQ1L3NSo@o1V7vGzOpFxyrkphAtmuPEU5H@wPWPsxTjmoRlDzpwzZgMZaWiMNnABwc8K2xozizlkhTSSIgMBzGbwnL0IYbGxbCsZT5aezH2Qf1Ps1h66Pd4KTMjCmMtYwd2OFDrfEesBEY0S7J8nyDQ/PhHs4RnxqG3R1zFhCyWk0yHhFMmZJOlWaYezlV/jy33S4X0JE@/r9EMJuaZVCMvL097@bzo6Pj7K7aWjul5Df9Kmp/vo1KxD6FpGLue71uoomxaaY0c@7hwNAiG2sqxc8a5Wkql@/84sLxJ4Q3tfVv4FoU5JG2bKVxgeYQus@o7rnaVq7isIttJmReAEVA2OEJUGDx0O0Wyzn/O08POCJxHN5xF/@UO//wA).

The Challenge
-------------

Given a regex in the format described above, return a regex in this format that matches precisely those strings that are *not* matched by the input.

One potential method to do this would be to convert the regex into a [nondeterministic finite automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton), then convert that into a [deterministic finite automaton](https://en.wikipedia.org/wiki/Deterministic_finite_automaton), flip which states are designated as accept states, and then convert it back to a regex.

Test Cases
----------

```
format:
input   => potential output
           equivalent infix regex

0       => _101|+_|;|
           |1.*
1       => _001|+_|;|
           |0.*
_       => 01|+
           .+
!       => 01|+_|
           .*
01|+    => _

01|+_|  => !
           [] (empty character class)
1001;;; => _01|01|01|;01|01|01|;;001|01|01|01|+_|;;;;01|101|01|01|+_|;;;;01|01|101|01|+_|;;;;01|01|01|001|+_|;;;;|||||||
           |.|..|...|0....*|.1...*|..1..*|...0.*

```