At the Equinox Gate, sentinels evaluate a layered web of runic conditions before opening the mountain pass. Each gate condition is stored as a recursive expression built from four primitives. Leaves reference a single rune symbol whose truth value is recorded in the nightly state ledger. Internal expressions combine or redirect evaluation based on that ledger. Sentinel scribes worry that a small mistake in the evaluation order will keep the gate sealed, so they have requested an exact algorithm.

The gate expression expr uses these forms:

• Leaf: a string rune such as "A". Its value is state[rune].
• NOT: {"not": sub}, yielding the logical negation of sub.
• ALL: {"all": [sub1, sub2, ...]}, true only if every subexpression is true. An empty list counts as true.
• ANY: {"any": [sub1, sub2, ...]}, true if at least one subexpression is true. An empty list counts as false.
• GATE: {"gate": {"check": rune, "true": subT, "false": subF}}, which reads the rune named in check and evaluates subT or subF accordingly.

All keys appear exactly as shown. The ledger state maps rune strings to booleans. Your task is to evaluate expr recursively according to these rules and return the final boolean result.

Example 1:

Input: expr = "A", state = {"A": true}
Output: true

Example 2:

Input: expr = {"all": ["A", {"not": "B"}]}, state = {"A": true, "B": false}
Output: true

Example 3:

Input: expr = {"gate": {"check": "S", "true": {"any": ["N", "E"]}, "false": {"all": [{"not": "N"}, "W"]}}}, state = {"S": false, "N": false, "E": true, "W": true}
Output: true