The question
A traffic jam doesn't stay in one place. It moves back along the freeway, and each sensor only sees the part passing over it. We wanted to know if a model that understands how roads connect could see a slowdown coming.
We used METR-LA: 207 freeway sensors in Los Angeles, each reporting speed every five minutes. The model gets the last hour and has to predict the next hour. We scored it with masked mean absolute error (MAE), the average gap in mph between predicted and real speeds, skipping missing readings. We checked 15, 30 and 60 minutes ahead and focused on 60, where the errors are biggest.
input past 60 minutes |#|#|#|#|#|#|#|#|#|#|#|#| 12 observations per sensor | model v forecast next 60 minutes |?|?|?|?|?|?|?|?|?|?|?|?| 12 predicted steps per sensor one cell = 5 minutes · all 207 sensors
The first approach
We inherited a model called SpectralMambaReal that scored 4.18 at 60 minutes. It turns sensor readings into graph frequencies with a graph Fourier transform, runs Mamba over them, and reads out a forecast.
Graph frequencies describe a pattern across the road network. Low frequencies change smoothly between connected sensors, like a whole corridor slowing down together. High frequencies are sharp local differences, like one jammed ramp next to clear roads. We also tried running Mamba across the frequencies, not only across time.
Every change landed in about the same place. We tried deeper models, wider channels, adaptive embeddings and new decoders, and got 3.72, 3.68 and 3.69. Our read was that the fixed, cut-down graph basis was the ceiling, not the layers on top of it. So we changed the foundation.
A stronger baseline
STAEformer learns an embedding for each sensor and for each time of day, then mixes them with attention across time and across sensors. It learns which roads affect each other from the data, instead of from a fixed map.
Our reproduction scored 3.339, matching the paper's 3.34. Averaging four separately trained models got 3.290. ST-TTC, a tiny 1,656-parameter calibrator that adjusts the size and timing of a forecast, took it to 3.283, the best public result anyone can reproduce. Picking from a pool of 24 models for each forecast length reached 3.2603 in our own tests.
SpectralMambaReal inherited baseline |############################ 4.180 Spectral v1 original spectral model |######################### 3.720 STAEformer our reproduction |###################### 3.339 Four-seed ensemble uniform averaging |###################### 3.290 + ST-TTC calibration reported public result |###################### 3.283 Diversity ensemble best internal result |###################### 3.2603 +---------+---------+---------+ 0 1.5 3.0 4.5 mph
One thing we were careful about: these gains came from averaging and calibration. They don't show that a new architecture beat STAEformer.
Three views of the road
STAEformer is strong, but it only learns road structure indirectly. We wanted to know if adding the structure explicitly still helped. So we froze STAEformer and trained a separate branch that learns a correction to its forecast. We called the hybrid STAE-Spectral-Magma.
Each view gets its own graph frequencies. The geographic view uses the physical road network. The directional view uses a magnetic Laplacian, whose complex numbers can encode which way traffic flows. The behavioral view links sensors whose learned embeddings are similar, even when they are far apart. Bi-axis Mamba reads across time and across frequencies. A small mixture-of-experts router decides how much to trust each view for each region and forecast length.
sensor history
|
v
+----------------------------+
| STAEformer |
| frozen backbone |
+----------------------------+
|
v
base forecast
|
v
+----------------------------+
| three graph views |
| geographic / directional |
| / behavioral |
+----------------------------+
|
v
+----------------------------+
| bi-axis Mamba + router |
+----------------------------+
|
v
learned correction
base forecast + correction = final forecastResults and limitations
On PEMS-BAY, a second traffic dataset from the Bay Area, the hybrid reached 1.550 validation MAE against STAEformer's 1.580. To check that this wasn't just extra size, we also trained a bigger plain STAEformer, which scored 1.583. Our hybrid has 2.08 million parameters: a little more than the baseline's 1.95 million, and far fewer than the bigger model's 3.45 million.
MAE 1.60 | | | | larger control 1.583 * 1.58 | * STAEformer 1.580 | | | 1.56 | | | @ our hybrid 1.550 | 1.54 | +----------+---------+---------+---------+ 1.5 2.0 2.5 3.0 3.5 parameters (millions)
On METR-LA, the same branch didn't help. Other ideas fell flat too. Scanning across frequencies gave tiny gains, a Gaussian likelihood loss did worse on MAE, and a Laplace loss closed only part of that gap.
We also ran an oracle test: if we already knew the perfect correction, could our frequency basis even represent it? That split one question into two: what the representation can express, and what a model can predict from one hour of history. Our best guess is that on METR-LA, STAEformer already captures most of the structure we tried to add, and the hour of input is the real limit. That doesn't prove no model could do better.
Takeaways
When several versions of an idea all score about the same, the next thing to try is a different idea, not a bigger version of the same one. Switching foundations is what moved our numbers.
We ended with stronger ensemble results on METR-LA and a correction branch that helped on PEMS-BAY, and we kept those two kinds of result apart. Writing up what didn't work as clearly as what did was part of the job.
The team
===-=====+++**###******+++===============+++*****###%%%##****++++++++++=======+===========------::::: . ..... .. =++++*****#########.::----:.. *%%%%#
+=====+++====---+######***+++=========++++****####+- -##****+++.... *###%%%#...........--.:: . . ... =********#########%- .::-==:..-%%###
:--==--:-:::--::*@%%#####***+++++===++++****###### *##****++ *%%%##%%.::- ...:-:::-:.... . . =*************#*###%*+: . ..:*%%#
----==-----:. :+%%######**+++++*********######%= ::=.:#####****. ...::::+**++*#%*######%%%%@@@@@@@@+:. .---: -#***####*######%%%%%@* ....=%%
#**%+:::::. .:. *%#######*+**=:....-=**#######%=.--++*#####****: . #@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%@@%=+=***- -###############%%%%%*.. .....::::-%
=-=.....:=-. .-===#%%########**= :+:*#######%%%.-==+%######***- . +@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@%-=+++*:.:-+############%%%%%. .....:::--=
+...:.--=-.:-=++==*%%########*#: ==+++=######%%%#= .-+.-*#%%###**= . =@###%####%##%####%%%%%%%%%%%%%%%@@+-:-=-- ....=##########%%%%= . .....::---
-:::::::::-*----=+%%%########*#*: ==+++=#####%+=:::. .= .:*##**+ . -@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@+... =- ....:-*########%%%% :## ....::--
+++++++****= :---:*%%%%########%#.**+++*#####+ ..... :##*** :@%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%@-..... ..:. ...*##########%@ .. ....::--
++++++*+=: :+ . :=#%####%#=. +*:.#####%: .... =%@% .*#*** .@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@+ ... ===: ...+######%##-+%. ...::--
+++++++. .. ....:. .%##%=:. ... - .=*#### ..... ...=#**# @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@* . .. ..-#######==-=-. ...::--
==+::-= . ........... =%%- ......... .. -##* . .......... .-%###. @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@+ . ..:%%%%%%#.:: ...... ..::--
++++++- .. .... .. %+ ... .......... ### ......... ::::- . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@. . .......:====--=%+++: ..........:--
=====+: . .... *:... .......... =##* . ........ - . . #@%%%%%%%%%%%%%%%%%%%%%%%%%%%@@#. .. ........ +%%%@ ..:-
++++++= . . ... # .... .......... ###. .. .........= *@@@%@@@@@@@@@@@@@@@@%%%%%%%%@= :* .. .%%#@ .+
=====++. ... * ... ........... +###- ... .......:%#*++- . =*****+++++++++++++++++++***#*+-.+#* . . *%#%- .:.::
===+++++. ..:*=:. .. += ... .......... :###+ -**: .**###*++++*++****+++++++==+============*+==++++- :++ .%#%- .....
++++++++* -**###*#*=#+ ... ......... =###+ :=**:::+*-##**++++++++***+++++++++++++++++++*+*++++++++.:: ....:--=====---::.... ..::-+*%
+=++++++- ---.*#- ............ ..+#*#- -+*++- ##*************+++++++++++++++++++++++++++++*. . -:. ... .-=++++++++++=:.:.:::-=###**##
-:-==*+*- .... .-. *##=............. ..***#+ :::.. --=-::***************+++++++++++++++++++++++++++++*. - --. ...************#+-::-=--==******#
:-=--#%+: ... .++- =#*#. ........... #**#* ::::::::.:-:***************+++++++++++++++++++++++++++++*- . .....+#########%%%==-..=+++=+#*****
-+--:+%#* .....=***. =#**#: :+. .. +*-*#***# :::::....:--****************++++++++++++++++++++++++++++*- .. ...+###########%=-- -==++=*+#*##*
:+---*%%%: .... ... =***# .#*+.....*+****#*#.:::::- ...::****************+++++++++++++++++++++++*++++*=..:::::::....*###########%+-: +**##++*+**##
....---+= .... =***# :--.....:=-#*****#..:::.+: ...:+=::.--=********++++++++++++++=+++=+++=******:::.::::::::..+###########%+-: *##%@+=#***##
:-::...:=* .... -**** . *#****#..:::.*- ...:=- =-+--#*******+++++++++++++++++*+**++***** ..:.....:::-:=%######%#%#%+-- *#%@@+=+#**##
+-:.:..:.#: ... -= =+***********- .. +#****#:.:::.*+ ...:==-*=*.:##******++++++++++*****+=**********- .......--:*%##%%#%#%%%+-- -**##++=*#*##
......:.:+- .. -* #:%+#######%%. . +#****#=..:::## ...:++--:-+#%%%#*******************+*********##. . . ....:-:::+++*****###+-- -=-:-+*+-*###
... ....=:-.. +%: + .:@%%%%%*#% .. =#****#=..::-## ...-########********************##+*##*#######* .....::-::..:....::::--:. :..:-=**==#%#
. . ....-+: .. :-= :. +@%%%%%%@# . =######+.:..-#* ...=****+*++*****#***********####*###########%= ........:-:::-@%%%%###**-:: :.:---+#*==#%
.. ..:::=+. --= ---%@%%%%%%@+---: =****##= .::=#* ...=##**+*++#****###**********##**############: ...:.:....::-:.*%######%%*:-.::=*+=-+##*+#
... . +**:-+=. --=. .:---------===*@@@@@@----:-:..:::-- ..*#---=+-=+*-====++++++****#**############%*.: ... ..:-:::%%######%*--.:--++*+++*###
....::*+::==+==----:.. :-----::::-*@@#*++++++-....:==:...*+::::*=+#%#%%%%%%%###**+=:::-----=====+++=.. . ...::.=%%%%%%%%*=-.::-+==++***##
.-*+=..-====-=*#%%%#####*###%%@*=: -******+ ..:+**..:.=+*%@@@@@%%%%%%%%%%%%%@@@@@@*------------=-:.. ... .:::==-+==++++++==. :---=+*****#
=#*:.::::---=*: :=+:-:.... -# ..-******+ .:=***: .**@@@%%%%%%%%%%%%%%%%%%%%%%@@@+++++++++=-==. .. . .. .. .:::----====---==. :----====*###
.-+##=:: .:---=*#: .:.::::.... # ..-*++++*-::::***+=*%%%%%@@@@%%%%%%%%%%%%%@@@@%%*+++++++*+ ... .. .. .::-=-----==+++==:.:--==+++***#
.:=+*#=--. **#*::..:::.:........ : +++++++*@@@#++++==+*##*+***#%###%%######**+++++++*****#. . . .. .. .-::---==-:... ---==+++**##
.. .:==-:==---+:.::......... . -*###*+*+. ........:::--====+:--===+++++++++++**-:-: .. .. .:::----######*=- ---+=+++**##
.........::=-----: ........... ...:-+=+****** .=+++++++++++++++*. ::........... . ... ..:.--:.*******==- -=:+++++**##
=+%*=@=+@#*-++*@@%+**#@%**@@%@@@@@@@@@##@%%%%%@+*******+++++++++++++=+=+=====-:::-====:=:--==--::::-::::::-=------------=====-----------------=-:::-=-
=+%*+@**%#*=+*#@@@%@@%@%%#@@@@@@@@@@@%##@%%%%%@+*******+++++++++++++-==+++====++++===-:::::-:::::::---:========+=-+++++++====------------===---=====--
=+%*-@--%**-=++@@%=***@%*#@@@@@@@@@@@@##@%%%%%@=******++++++++++++--...-=+++==========-:::::::::::-===-=+======--.---::::::::......:::::-:-----=======
=+%*+@+=%#*-=++@@@*###@%**@@%%@@%%%%%%##@%%%%%@:+++****+++++++++++:... -+++=+========--=+===----------=----===+++++*****###%%%%%%%%%%%%+:---========
=+%**%+*%#*=+**%@@%%%%@@%%@@%@@@%%%%%%##@%%%%%@-====+=*++++++++++=.... +++++===============-#######%%%%%%%%%#%%%%######%%%##*#########+ .........:.
=+%==%=+%*+:+++%@%+***%#+=@@+%@%##%#**##@%%%%%@-======++**##%####=. .. +++++===============-##################################*******#* ....:::::::
=+%=+%=+%**-+++%@%*##*%%#*@@#%%%##%##**#@%%%%%@:===:. :-+%%#*++*#+*-.:.:=++++++++++++=======-:##########################################* .....::::::
==%=+%=+%*+=+=+%@%**##%%##@@#%@@%%%%%%##@%%%%%@:==:........:=*+-: ..:-=***========------:::::.#########******############################ ......:::::
==%--%--%*+-=-=%@%=+++%#==%@=*%%#####**#@%%%%%@-=- .:..:... ... =***-----::::::::::::: ######*******############################## .......::::
==#=+%++%*+-=++%@@#%%#%%%#@@%@@@@@%@@@##@%%%%%@:=:.::... ... ... . -::-------::::::::::: #####*********###########+#***############% .......:::
==%--%-=%*+:=-=%@%+**+%#++%@=*%%**##***#@@@@@@@:*.::. .. .: ..-:-:... :-::::::::..... *###*****#****############################% ......::::
==%==%==%*+-==+%@%+*#*%%**@@##%%#%%%%%##***++++:.:::.:. .=-++-:=-:--:: ....: :......... . . +##*************##########################%
==#+*%+*%**=***%@@%@%%@@%%@@%%@@%%%%%##:.. .:::..:=**+++++...::::* :-----++==---:::..... +#***********#############################%.--===++++++
=+#:=%-=%*+:==+%@%=+**%#**%@*#%@##%%##:...... :::::::...=+===+. ...:-*=.:-:===#%##########***+-#*********###############################%.===++++++++
++#+*#**#**+***#%%#%########**********..... .:::....... --=:-.:.-==== :-::-.:**++++++++**++*:#*############***##***####################:======+++++
**************++++++++++++++++++++++-=... .::........... .++-=--:=--=== ..:. :+**++++++++=+:###############***#****##########*.*+.%##%:===========
+++++++++++++++++++++++++++++++++=--::... ::........ . :+=--==-=:-==+= .: .. .-:::.*+++++:----------======+++****#########%+ ##-=----********
++++++++++++++++++++++++++======.:::::....::...... . :*=-====. :--=-: . ::.:......#*********+=========----::::.....:::::--:-==:::===--= =*****
++++++++++++++++++++***+==.... ..:...::....... .+=:===. .::. ....::......=++++++++++=-===+++++++++++++++======--= ..=-- :====+
++++++++++++++++****+++====...:::.... .::...... .. ==:=- .------:=.........-: =+++======-=++++======================+...... ... ..:=====
++++++++++++=++*+=====-==+--.. ... .::..... .-=+++++ ...:::...... :+........:==-+*+=+****++++++++++++++++++++++++++===+......:. -+++++
+=++++++++++-=====--===+===-: . ::... .:-====+: ..-:...:::: ... .===-+=-:.-+===++++++++++++++++++++++++++++*.. :-::****- -+++==
+++++++++++=-====++=---==-*+--.. .:..... .:.:-====----.==:.. ... - .:--===.+++=+=++**********++++++++++++++++++++++*..===:*******++++=-:-
+=++++++++==-==+++=+-----=+:-=. ...... ==++=-===--===++++**++++++=-:++=-:=:==--+=+***+++*************++++++***++++++::--::++++++++=-::--+
++++++++++=-====++=++-==--- .-.. .. ... :===.---=++. .+=+++===--+*****************************************+++++*++=:......:-
+++++++++=======++++++-::-. .. ...... .:-=+===+++- =+++++====-*+*+***********************************++****++=:.....:::::-
+++++=++=-========+++++--- ... :--+++**********************+++=----****************************************++++-:. ......::::--
+=+++============++++++=+: .. ... .. .::-=+++***********##########*************************************+++++==-:...::::::::::::-:
==================+++++++* ... ..:... .. ..::---===+++++++++++++++++*********+++*+*++++++++++====--::......::::::::::::::===
==++++++==========+++++==- ................. ......::::::::::::::...... ..........:::::::::-=--
*++=-:.===========++++=:-+*+-....... ........... . ...:::::::..:.:---
.===--=====+++=--=+++*+:-::::. ............ ...::-:----=
+=-=---====++-:--===-=: . . . ............. .:--=
.... :======-=====:.:------=. ................
.... ===========-: .:-::---- ............. ..
.....=--=======-: .::-:::-- . .......... ....
....:===--====--. ..::::::-- .... ............... ....
....-========--..:::--:-----.. .::.......:..:::.. ......... ...... .. .
....=======---: .:::::..:::. . ... . :. ...... ...... ..
...:-======--.. . .. . . .... . :.... .: .... . ..
...-=-===--::.... . . . . .. . .. ...
...-=-==-:::........... . : ..... . . .:... ..... .
:..=+=---::.....:.:...... : .. . .:. . . .
...:==--::.........:..... ....... .: :. . .. .. .. . . .
...=-:::................: ... : -. . . ..... .. . .
..==:::.............::: . . . ............ ...
*++*#%=.#*=.+***+*+++=*+++++++++++*+************#######*****************+=*****************###########**************+******************+******+*******
+*%+..::. .-*= -=**++++++++++++++++++++*******#############*************+=*************##################***********+*+++++*+++***********************
*%@ -*-:..+%#+=- .+%#**+++++++++++=++++*****#######%%###########***++++++=+++++++****####%%%%%%%%%%%%%######******+*+++++++************************###
+=+*#@+::*=*:.:-++: -=##+++++++++==+++****########%%%%%%@@@@@%%%%%%%%%%%%%@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%######*****+++++++++++*++++************######
+###=: ... ++++. .===-:+++++++::===+***###########%=-------------------------------::::::::::::%@@@@@@%%%%%%%#####**+******+++++++************#######%
%#. .+*+:-=#*#%:...+*++++++++==:==+++=--++#%######%=:-------==-====-=--=-===-=-===+==++++++===-@%%#++*@@@%%%%%######+***********************########%%
*--+#*=++==:.:+*=:-:-=++++===-::-=- .=%%###%%=:------==+=#%##+##*#*%##*#+#*+#++++++=----:= .. =@@%%%%%%####********+=--=--=+*****#######%%%%%
+%#*=:.:#.=-+* --==- -.===:::.. :-. =%%##%%+:--------===-=====--=====++==============-......... -@@%%%%%%###*******-:: .-=-#########%%%%%%%
+%...=+#@#*+=*=-:.::-+=-===---:: :.::-=:. *%##%%*==++++++**######%%%%%%@#+---======---::::. ..-===-...@@%%%%%%%%#*##*##:.:--*=-:::.:*#######%%%%%%%
@@+.:@%#+-=..:-::==++.=+-::..:=+-::-+=-+-::. *%##%%*--=+++**##%%%%%%%++*%@+:--====-==++=--::::*=:.=-.-= +@@@%%%%%%%%*####+ ..:#@%+:..::-%####%%%%%%%%%
=-::::.: -+..::. .. ::. . .:::-=--:=++::%%###@+-:.:.-+*++*=+=+*===++-:-----:--++++:::.::*#+--+++*+:@@@@%%%%%%%%*####+ .::..*:.::::-%####%%%%%%%%%
.+##-:.-*+: .. ... .:.:--:. . .:-=-----=-=####- .+%+*:--=+=+++#++=+*-**==---=++++-:::::::--:.-==-+++@@@@@%%%%%%%#####%=.-=-:@*=*#-:#%%%%%%%%%%%%%%
*=-...:#@#+::-::. =%@#*+=: .:..:-::..*##+#%: -+++=: +*###%#+-*:....-==++*+=..::::.::::::=++=+@@@@@@@@%%%%%%######%==+=-+*++#+#%%%%%%%%%%%%%%%
#@@**#*#+=+-:::-..::: +**++**+=: --:.::. .=-=*#%. :==*+--. ..:=*+:. =+++++:=---:::-=--=:-=::-::---=+#@@@@@@%%%%%%%#%%%##%*:=:-=*==++%%%%%%%%%%%%%%%@
+=:=%#%%-.:.:...::.*#*%@%##@**+- =*+=+* . .:=*#%*:++==++#%-.===+=*+. ---+=:=:=:----=#*+**+*-::-:==+=:.#@@@@@@%%%%%%#%%%%%%%#---+%%++@%%%%%%%%%%%%%%%@
-=#%#+=**#=....::..:*#*+=+**+*#- .@*- :::.:. ::+-====+=--===+=++. ==-=++*+:-=##++#+=++=*=---:-:. =.=.-+#@@@@%%%%#%%%%%@*:---====*=*%%%%%%%%%%%%%%@
*#+-:...+*=-::::... :+**+**==+= . .... -=+++++:+++******..=+-+*=++. :+***+=+-+=+=+:.-*.-:-+:*... .:*@@%@%@%*+-:..---==-+%+==+*%@@%%%%%%%%%
.....:::........ ...*+:=*#*++= ..:++++*.. .--==-: .=++*+***-.:===+++:..-*****+-==+=+-: : .+==++:..:::.-@@: =.:+ ...-=::-*%:.+*-=-=+*#%@%%%%%
==-.:--::. ..::::..=+--==: .. :@@@@@. -=-=+=**--+++*++=:.==+++::=+*+++*-=-=====+: --. ==+#=..:::::*= ==-+.-*: -#@@##+:-*+===---=%@%%%%
==+=:=*#%###++++...:. :=++: ::::--==- =*+==:. -+*+-...-+*+++:.:==+=-::.:=*=-==+*:...:::: :++*+**.. .=*.:**#==#----=-==@%%%%
=.:::=++++=-==+=+*--:. .+. .....:... --=-:-=: ###+: .++: .*-###+. :-=+=:::..*%*====++ ...:. -==+****#*:--::-*=++#=#%*--:::-%%%%%
: .. ...-+---:-==-:-::.:. . . :: . . ..:. ##*#= ...:*+..::#*+#+:- -=++. .... :==+*+ ... ===++*+-.::-:::.@%%===+#@% :--:#%%%%
=-: .:-----:-=:::::.:*#:. .#.*:-.... . :##**:.....*=....***#+:-..-++. ... . -++*= .. ==+*#+..:::.::-.#%+===++*#----:#%%%%
-:-. ..:::::.::=##=+*-.. . = :**#=*= ... :--.= .#*#%:.:::.=:-#*++**#+-:::-++. .. .. .==+*: .-+*+ ....:.:-::. .-==+*#*.:--:%%%%%
*:.: .::..+@@@#**+==-.. . #-++ #%#*++.-=.. -+#.# #### ::::...+%%%#*##-.:.--++: . -=-: . .-=** .....::--:....:=++**-:-::%%%%%
+.... :*@#*++++++-:. ..#:#+# .#*++*+=: . -+*+**#: **#= ::::::.. *##+...:=++- .. .. .==+#= ... .. .......==++*..::@%%@=
:.. .:===++*+=:...::. +*.**#@ =***+ =*++*#* .**%+ :::::::::...###@.. -=++- .. :==. .... .........======:. *%%%
...::.*#+==++***+=-:........ .***** =**+=: .:=+-.::::...:::. :.:=-. :. .. . .............. :+==-.:: #%%%
......#**+**+-:....::..:.... .***- . . :.::...::....::. .::---- - ............... .. *%%%
+**+-. ....:::::. ... +#* .--:..::...::::.. .:-::=*+=* . ==-*%#- . .................... *@%@#-
.: ......::. ... :*=.- := ... ..: .:..::::::. ....-=+**- . @%###%%* ............... . .*@%#==
--: .. .:......##**- .:::.*= ......... :-: ...........:..--====+* ######%: ......... . ... #@@%*-+==
-++ .:.. .:*+++=+*****-*= ........... :=. .....:::::::..=====++ *#####% .......... .. *@#=-=+++
:+. ... ... -++=+=++**+*+=-: .......... .: ....::::-----::----== =%####% .. . ====+++-
=- .....:. -+++==+*#***+-. .......... :. :::::::----------=--= ... . .%####% ... ... . :+**+=:
*: ...::..... ........:-*+++*+*#*###*+=. . ...... -. .:::::::--:::::--:=-== .... +###%* ...... . .. :- .
=. ....... ........:++++**+******#*: ....... -: ...::::::::::::::: ===-. . .... =#*#% ....... ...-.
= ............. -*+****=**+****+: ...... :. .::::::::-------: .=::................. ....***#% . ..... ....@@@#+:
..:.....::::::::. ... +****+=*++****+:. ... -. .:--------::. =- ...:..:.:::..::.: .::.***#+ #%%%%@=
.............. .......... -*******+****#+.. ....... : . :+ ..::.::..::::::::. ::.***#+ . *%##%@
................ ......... ****+*++****#=.. .......:....... . :+..:::::....:::::::: ::.#**#%: =%%%%%
..:::::........... ........+***++=+****#=.. ......... ...... -+:..::::....::::::--::::#**#%- ... .. :@%%%=
. .....................:::.:**+*++*+***#+ . ....... ...... .- .++:..::::... :::::::::::#**#%+ ...... ... :@%#@.
- .....::::::.........::::.##=++*+++**#+ . ....... ...... :+= .. +++= .::::... .:--::::::.#**### ......... .......:%%%% .
- ......::::::::.. .....:::.*#-++++++++** . ...... . .... -=-: ... -++++.::::::.. #.:::::::: #**##% ......... .......:@%%% .
-: .....::::::::.......::::.+*=++++*+++*+ ......... ... -..- .... +++=+::::::::...@ :::::::: #**##% ........ ..... ..%%%@
--:.....:::::::::......::::.++=++++++++*+. .......... ......::: ... .*++++-::::::::.:@:.::::::: #**##%. ........ # . . . #%%@
:::... .:::::::::.....:::::.#-:=*+*+++++=. .........: ...... -. ... .-=:.:-.::::::..-%-.:::::::.#**##%- ....... @= .... .... #%%@.
:::... .:.::::... ......::.:%.:+****+++=-. ........:- ..... +***#= .... =++:===::::::::.=%* :::::::-***##%= ....... @%. ........ :%%%%-
:::.. ........:........::.-%:=++++++++=............:- ......=++**#. .....--+----::::::::.+##..:::::.+***#### ....... :%%* ........ +%%%%*
:::.. .....:..: .....::::.-%-:+++++++= ...:........:-. ......==+**#* ....-=-:: ::.::.:::..+##-..::::.=***###%........ =%#%- ........ =%##%%
:.... ..::.:::. ....:::::.=%--++++=*#+ .............: ....:--==+++ ... :-.... ...::::..=##=..::::.-***###%-....... *%### .........:%#%%@.
:.... ...:..::. ......:::.+#--+++++##= ... .:...... . .......::- .....:...:---:.::::::...::.:::::.:#**###%= ...... ####%: ........:%###%-
.... ....::..: ......:::.##--++=+*##= ... .:..... . ..... .:....::-. .....::::-::...::::::.-:::..::::..**####%= ...... ####%* .........####%:
..........::..: ......:::.-## --++**##- ....:::.. ....:......::-. .......:::::::..:::::::.==--..::::..:::=+*%-....... %####% .........+%##%:
..........::... .......:.=#% --=*####--==-....::... .. .....:.:.---:+- .........::==++=-::::::::.====.::::::.:::::::....... .%####%..........+%##%:
...........::.. ......:.##% :-=*####=----....:::.: ................:-...........:...........:::..----.::::::.::--=== ...... **##%%: .....::.=%##%-
. ... ......:. .....::.-## :-+*####-----....::.:+:-...:::::.-======+ .....:::.-+========+:....:.-==:..:::::.-+++++- ....... :::-=+: .....::.=%##%-
............::. .....::.=%* :=++####-==++....:::.@@@..::::::.@@@@@@@@ .::..:::.@@@@@@@@@@@-..::: =+*:..::::..=****#= ....... ==-:::. ........+%##%-
............::. ....::..##- ===+###*=++++....::=:%+ ..:::.=#******+ .::::::..#*++++++++=:--:::.###-:.::::..+****#. ....... ======: ........=*##%-
..........::::. .....::.+##+ +==-###*-----:...::..=. ....:. =+++++++++ ..:.:::.-*+*******+ .::::::#*#+::.::...*****# ........ *#*++=- ........--:-=:
..........::::. ....::::####---=+***+-=--....:::...:......:-=++=++++*+ ..:.:::.+*++*+++*#%=:....:=**#+.:::::.=*****# ........ *#*###* ........==---:
..........::::. .......+#**#+:=++*#%*-:-:-.....:::::...-+%##*##++++**.....:::::***+++#%%%%@@#***+++**=.:::::.+###**# ........ #****## ........+===+-
... ......:::. .......+##**#====+-=@@*--==-.:---...::-===##%@@@%****+ ....:::.=***+*%@@@@%%%##*==-====::::...++****#......... ******#= ......:%#**+=
....:......:::: .......-*****-.. =+ +%%%%===##%%@*----+++==*#%%%%*++==...::::.:+****+#@@%%%%*=-=====+++#%@%@#*-======......... +*+***##-......:%####%
::-::......:::: ....:.. +*+*+=.:+: -%@%%#.-#@@@@%==+****++++++++=-=+=++:-:::.-==++++=-=+*#**##+=======+#%%###*=======...........******#%....:.-%####%:
-::::......::::.......:+*#=-. *.+*.:...-++=#%@@%%+*******************+-.-=:::====+++++++*#####+=+++===%@@%%%%*-+++++++.........:=++***=....::.-%#####=
::::::.....::::.......=*=*###*@-#+--:---:-=+#%#*+*********************:::.-+#***++==+====+++*********=#@@@@%%=======+**=--:...-======..........*######
--::--...:.::::--...:+#*=.:+###.%--==++*****+=+*##********************-:-*#*****++++++++==++++*******+=*#%#*=======+**#####*----=====.......:::.######
:-----.......::--+*+%#%%#*= =+:-+--**********************************#*******++++++++++++++++**********++++**++====########----======--+==+-: :######
------:.....:=+*++=+%##@@@@@-::--==*******************#***********+++*******+++++++=++********************#******++%%%%###*-=====++++=*#%@%@@#+#######
-------+++*##%%##-::+#%@@@@@@*****##***************************************+*****+++++****************************++*%@%%#+===========**#%%##%+******#
====--=+*%##%%%%%*-==*#%%%@%**###***************************##***********+++***+++++*********************************++**++==----=====*#%%####**######
+=====-+**%%%##@@@@###***+++###*********************************##**#*##*****+*********************##***++************#**++=======-===#%%%%###*#######
******++=+#%%@@@@@@%##########**************************************##*#####********#####################*****####*******++++++=====++==*##**+******##
*******#*+*###%%%@@@#######******************###**********************#########**###**############%###**********####***++=++++++++++++*+=--=++========
*************##%%#++*#######***************#**####**********************###**###***##############%%%####***+++**##*********++++++***#**++**+=========:
********#####**++*#*###*###******************####**####****#************##**##*##*+******#######%%%%%%%##****++**######********+++********++======--:.