Prerrequisitos
Para poder utilizar el prophet junto con la metodologÃa de tidyverts, es necesario descargar fable.prophet. Al momento, esta paqueterÃa aún no está disponible en CRAN, por lo que se debe descargar desde Github:
# install.packages("remotes")
# remotes::install_github("mitchelloharawild/fable.prophet")
library(tidyverse)
library(lubridate)
library(tsibble)
library(feasts)
library(fable)
library(fable.prophet)
library(plotly)
Introducción
Prophet es un algoritmo diseñado por Facebook para crear pronósticos automatizados.
Prophet is a procedure for forecasting time series data based on an additive model where non-linear trends are fit with yearly, weekly, and daily seasonality, plus holiday effects. It works best with time series that have strong seasonal effects and several seasons of historical data. Prophet is robust to missing data and shifts in the trend, and typically handles outliers well.
Existe la paqueterÃa en R prophet para crear pronósticos con dicho algoritmo. Sin embargo, para trabajar con la misma metodologÃa del tidyverts, crearon la paqueterÃa fable.prophet que crea una interface a fable.
Pasajeros en LAX
Carga y limpieza
Compararemos los pasajeros nacionales e internacionales de vuelos en el aeropuerto internacional de Los Angeles (LAX).
# Read in the data
lax_passengers <- read.csv("https://raw.githubusercontent.com/mitchelloharawild/fable.prophet/master/data-raw/lax_passengers.csv")
# Tidy and summarise the data for comparison of international and domestic passenger counts
lax_passengers <- lax_passengers %>%
mutate(datetime = mdy_hms(ReportPeriod)) %>%
group_by(month = yearmonth(datetime), type = Domestic_International) %>%
summarise(passengers = sum(Passenger_Count)) %>%
ungroup()
`summarise()` regrouping output by 'month' (override with `.groups` argument)
Convertimos lax_passengers a tsibble para poder utilizarla con la metodologÃa de fable.
lax_passengers <- lax_passengers %>%
as_tsibble(index = month, key = type)
Exploración de los datos
Ya que es una tsibble, podemos graficar las series fácilmente con autoplot().
lax_passengers %>%
autoplot(passengers)

Las series parecen tener una tendencia por partes (piecewise) y estacionalidad multiplicativa (ya que aumenta la estacionalidad con el nivel de la serie).
Modelado
El modelo prophet puede contener:
- Tendencia lineal o exponencial por partes.
- Estacionalidad aditiva o multiplicativa.
- Efectos por dÃas festivos.
- Regresoras exógenas.
Consultando la documentación ?prophet podemos ver más detalle sobre cómo se puede definir el modelo.
Para especificar un modelo con tendencia lineal y estacionalidad anual multiplicativa, podrÃamos usar:
prophet(passengers ~ growth("linear") + season("year", type = "multiplicative"))
O, si quisiéramos que R encuentre automáticamente la especificación del modelo, simplemente no definimos el lado derecho de la fórmula:
Los modelos se ajustan de la misma manera que antes (a través de la función model).
fit <- lax_passengers %>%
model(
Prophet = prophet(passengers ~ growth("linear") + season("year", type = "multiplicative")),
`Prophet auto` = prophet(passengers),
ARIMA = ARIMA(passengers),
ETS = ETS(passengers),
Harmonic = ARIMA(passengers ~ fourier(K = 3) + PDQ(0,0,0)),
SNAIVE = SNAIVE(passengers)
)
fit
Componentes
Igual que con los modelos de descomposición vistos anteriormente, podemos utilizar components() para extraer los componentes de la serie.
fit %>%
select(Prophet, `Prophet auto`) %>%
components()
fit %>%
select(Prophet, `Prophet auto`) %>%
components() %>%
autoplot()

Con
fit %>%
select(Prophet) %>%
components() %>%
ggplot(aes(
# Plot the month of the time index (month) on the x-axis
x = month(month, label = TRUE),
# Plot the annual seasonal term (year) on the y-axis
y = year,
# Colour by the passenger type
colour = type,
# Draw separate lines for each type and year
group = interaction(type, year(month))
)) +
geom_line()

Pronóstico
Es exactamente el mismo procedimiento que antes para generar pronósticos para estos modelos.
fc <- fit %>%
forecast(h = "3 years")
fc
fc %>%
autoplot(lax_passengers %>% filter_index("2015 jan." ~ .), level = NULL)

p <- fc %>%
ggplot(aes(x = month, y = .mean)) +
geom_line(aes(color = .model)) +
geom_line(data = lax_passengers, aes(y = passengers)) +
facet_wrap(~ type, ncol = 1, scales = "free_y")
ggplotly(p)
Otra manera de graficarlo:
lax_passengers %>%
autoplot(passengers) +
autolayer(fc, level = NULL) +
theme(legend.position = "top")

El desempeño del modelo se puede revisar de igual manera con accuracy():
accuracy(fit) %>%
arrange(type, RMSE)
Cafés
cafe <- tsibbledata::aus_retail %>%
filter(Industry == "Cafes, restaurants and catering services")
cafe
p <- cafe %>%
ggplot(aes(x = Month, y = Turnover, color = State)) +
geom_line()
ggplotly(p, width = 800, height = 600)
fit <- cafe %>%
model(
prophet = prophet(Turnover ~ season("year", 4, type = "multiplicative"))
)
fit
fit %>%
components() %>%
ggplot(aes(x = Month, y = trend, color = State)) +
geom_line(size = 1)

# fit %>%
# components() %>%
# ggplot(aes(x = Month, y = year, color = State)) +
# geom_line(size = 1)
fc <- fit %>%
forecast(h = 24)
fc
cafe %>%
select(-Industry) %>%
autoplot(Turnover) +
autolayer(fc) +
theme(legend.position = "bottom")

LS0tDQp0aXRsZTogIlByb3BoZXQgYW5kIGBmYWJsZWAiDQpzdWJ0aXRsZTogIkZhY2Vib29rJ3MgZm9yZWNhc3RpbmcgcHJvY2VkdXJlIg0KYXV0aG9yOiAiUGFibG8gQmVuYXZpZGVzLUhlcnJlcmEiDQpkYXRlOiAyMDIwLTA3LTA1DQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRoZW1lOiBkYXJrbHkNCiAgICBoaWdobGlnaHQ6IHRhbmdvDQogICAgdG9jOiBUUlVFDQogICAgdG9jX2Zsb2F0OiBUUlVFDQotLS0NCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoZmlnLmhlaWdodCA9IDUsIGZpZy53aWR0aCA9IDkpDQpgYGANCg0KIyBQcmVycmVxdWlzaXRvcw0KDQpQYXJhIHBvZGVyIHV0aWxpemFyIGVsIHByb3BoZXQganVudG8gY29uIGxhIG1ldG9kb2xvZ8OtYSBkZSBgdGlkeXZlcnRzYCwgZXMgbmVjZXNhcmlvIGRlc2NhcmdhciBgZmFibGUucHJvcGhldGAuIEFsIG1vbWVudG8sIGVzdGEgcGFxdWV0ZXLDrWEgYcO6biBubyBlc3TDoSBkaXNwb25pYmxlIGVuIENSQU4sIHBvciBsbyBxdWUgc2UgZGViZSBkZXNjYXJnYXIgZGVzZGUgR2l0aHViOg0KDQpgYGB7ciBwa2dzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KIyBpbnN0YWxsLnBhY2thZ2VzKCJyZW1vdGVzIikNCiMgcmVtb3Rlczo6aW5zdGFsbF9naXRodWIoIm1pdGNoZWxsb2hhcmF3aWxkL2ZhYmxlLnByb3BoZXQiKQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KGx1YnJpZGF0ZSkNCmxpYnJhcnkodHNpYmJsZSkNCmxpYnJhcnkoZmVhc3RzKQ0KbGlicmFyeShmYWJsZSkNCmxpYnJhcnkoZmFibGUucHJvcGhldCkNCmxpYnJhcnkocGxvdGx5KQ0KYGBgDQoNCiMgSW50cm9kdWNjacOzbg0KDQpbKipQcm9waGV0KipdKGh0dHBzOi8vZmFjZWJvb2suZ2l0aHViLmlvL3Byb3BoZXQvKSBlcyB1biBhbGdvcml0bW8gZGlzZcOxYWRvIHBvciBGYWNlYm9vayBwYXJhIGNyZWFyIHByb27Ds3N0aWNvcyBhdXRvbWF0aXphZG9zLg0KDQo+KlByb3BoZXQgaXMgYSBwcm9jZWR1cmUgZm9yIGZvcmVjYXN0aW5nIHRpbWUgc2VyaWVzIGRhdGEgYmFzZWQgb24gYW4gYWRkaXRpdmUgbW9kZWwgd2hlcmUgbm9uLWxpbmVhciB0cmVuZHMgYXJlIGZpdCB3aXRoIHllYXJseSwgd2Vla2x5LCBhbmQgZGFpbHkgc2Vhc29uYWxpdHksIHBsdXMgaG9saWRheSBlZmZlY3RzLiBJdCB3b3JrcyBiZXN0IHdpdGggdGltZSBzZXJpZXMgdGhhdCBoYXZlIHN0cm9uZyBzZWFzb25hbCBlZmZlY3RzIGFuZCBzZXZlcmFsIHNlYXNvbnMgb2YgaGlzdG9yaWNhbCBkYXRhLiBQcm9waGV0IGlzIHJvYnVzdCB0byBtaXNzaW5nIGRhdGEgYW5kIHNoaWZ0cyBpbiB0aGUgdHJlbmQsIGFuZCB0eXBpY2FsbHkgaGFuZGxlcyBvdXRsaWVycyB3ZWxsLioNCg0KRXhpc3RlIGxhIHBhcXVldGVyw61hIGVuICoqUioqIGBwcm9waGV0YCBwYXJhIGNyZWFyIHByb27Ds3N0aWNvcyBjb24gZGljaG8gYWxnb3JpdG1vLiBTaW4gZW1iYXJnbywgcGFyYSB0cmFiYWphciBjb24gbGEgbWlzbWEgbWV0b2RvbG9nw61hIGRlbCBgdGlkeXZlcnRzYCwgY3JlYXJvbiBsYSBwYXF1ZXRlcsOtYSBbYGZhYmxlLnByb3BoZXRgXShodHRwczovL2dpdGh1Yi5jb20vbWl0Y2hlbGxvaGFyYXdpbGQvZmFibGUucHJvcGhldCkgcXVlIGNyZWEgdW5hIGludGVyZmFjZSBhIGBmYWJsZWAuDQoNCiMgUGFzYWplcm9zIGVuIExBWA0KDQojIyBDYXJnYSB5IGxpbXBpZXphDQoNCkNvbXBhcmFyZW1vcyBsb3MgcGFzYWplcm9zIG5hY2lvbmFsZXMgZSBpbnRlcm5hY2lvbmFsZXMgZGUgdnVlbG9zIGVuIGVsIGFlcm9wdWVydG8gaW50ZXJuYWNpb25hbCBkZSBMb3MgQW5nZWxlcyAoTEFYKS4NCg0KYGBge3J9DQojIFJlYWQgaW4gdGhlIGRhdGENCmxheF9wYXNzZW5nZXJzIDwtIHJlYWQuY3N2KCJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vbWl0Y2hlbGxvaGFyYXdpbGQvZmFibGUucHJvcGhldC9tYXN0ZXIvZGF0YS1yYXcvbGF4X3Bhc3NlbmdlcnMuY3N2IikNCg0KIyBUaWR5IGFuZCBzdW1tYXJpc2UgdGhlIGRhdGEgZm9yIGNvbXBhcmlzb24gb2YgaW50ZXJuYXRpb25hbCBhbmQgZG9tZXN0aWMgcGFzc2VuZ2VyIGNvdW50cw0KbGF4X3Bhc3NlbmdlcnMgPC0gbGF4X3Bhc3NlbmdlcnMgJT4lDQogIG11dGF0ZShkYXRldGltZSA9IG1keV9obXMoUmVwb3J0UGVyaW9kKSkgJT4lDQogIGdyb3VwX2J5KG1vbnRoID0geWVhcm1vbnRoKGRhdGV0aW1lKSwgdHlwZSA9IERvbWVzdGljX0ludGVybmF0aW9uYWwpICU+JQ0KICBzdW1tYXJpc2UocGFzc2VuZ2VycyA9IHN1bShQYXNzZW5nZXJfQ291bnQpKSAlPiUNCiAgdW5ncm91cCgpDQoNCmxheF9wYXNzZW5nZXJzDQpgYGANCg0KQ29udmVydGltb3MgYGxheF9wYXNzZW5nZXJzYCBhIGB0c2liYmxlYCBwYXJhIHBvZGVyIHV0aWxpemFybGEgY29uIGxhIG1ldG9kb2xvZ8OtYSBkZSBgZmFibGVgLg0KDQpgYGB7cn0NCmxheF9wYXNzZW5nZXJzIDwtIGxheF9wYXNzZW5nZXJzICU+JSANCiAgYXNfdHNpYmJsZShpbmRleCA9IG1vbnRoLCBrZXkgPSB0eXBlKQ0KYGBgDQoNCiMjIEV4cGxvcmFjacOzbiBkZSBsb3MgZGF0b3MNCg0KWWEgcXVlIGVzIHVuYSBgdHNpYmJsZWAsIHBvZGVtb3MgZ3JhZmljYXIgbGFzIHNlcmllcyBmw6FjaWxtZW50ZSBjb24gYGF1dG9wbG90KClgLg0KDQpgYGB7cn0NCmxheF9wYXNzZW5nZXJzICU+JSANCiAgYXV0b3Bsb3QocGFzc2VuZ2VycykNCmBgYA0KDQpMYXMgc2VyaWVzIHBhcmVjZW4gdGVuZXIgdW5hIHRlbmRlbmNpYSBwb3IgcGFydGVzICgqcGllY2V3aXNlKikgeSBlc3RhY2lvbmFsaWRhZCBtdWx0aXBsaWNhdGl2YSAoeWEgcXVlIGF1bWVudGEgbGEgZXN0YWNpb25hbGlkYWQgY29uIGVsIG5pdmVsIGRlIGxhIHNlcmllKS4NCg0KIyMgTW9kZWxhZG8NCg0KRWwgbW9kZWxvIGBwcm9waGV0YCBwdWVkZSBjb250ZW5lcjoNCg0KKiBUZW5kZW5jaWEgbGluZWFsIG8gZXhwb25lbmNpYWwgcG9yIHBhcnRlcy4NCiogRXN0YWNpb25hbGlkYWQgYWRpdGl2YSBvIG11bHRpcGxpY2F0aXZhLg0KKiBFZmVjdG9zIHBvciBkw61hcyBmZXN0aXZvcy4NCiogUmVncmVzb3JhcyBleMOzZ2VuYXMuDQoNCkNvbnN1bHRhbmRvIGxhIGRvY3VtZW50YWNpw7NuIGA/cHJvcGhldGAgcG9kZW1vcyB2ZXIgbcOhcyBkZXRhbGxlIHNvYnJlIGPDs21vIHNlIHB1ZWRlIGRlZmluaXIgZWwgbW9kZWxvLg0KDQpQYXJhIGVzcGVjaWZpY2FyIHVuIG1vZGVsbyBjb24gdGVuZGVuY2lhIGxpbmVhbCB5IGVzdGFjaW9uYWxpZGFkIGFudWFsIG11bHRpcGxpY2F0aXZhLCBwb2Ryw61hbW9zIHVzYXI6DQoNCmBgYHtyLCBldmFsPUZBTFNFfQ0KcHJvcGhldChwYXNzZW5nZXJzIH4gZ3Jvd3RoKCJsaW5lYXIiKSArIHNlYXNvbigieWVhciIsIHR5cGUgPSAibXVsdGlwbGljYXRpdmUiKSkNCmBgYA0KDQpPLCBzaSBxdWlzacOpcmFtb3MgcXVlICoqUioqIGVuY3VlbnRyZSBhdXRvbcOhdGljYW1lbnRlIGxhIGVzcGVjaWZpY2FjacOzbiBkZWwgbW9kZWxvLCBzaW1wbGVtZW50ZSBubyBkZWZpbmltb3MgZWwgbGFkbyBkZXJlY2hvIGRlIGxhIGbDs3JtdWxhOg0KDQpgYGB7ciwgZXZhbD1GQUxTRX0NCnByb3BoZXQocGFzc2VuZ2VycykNCmBgYA0KDQpMb3MgbW9kZWxvcyBzZSBhanVzdGFuIGRlIGxhIG1pc21hIG1hbmVyYSBxdWUgYW50ZXMgKGEgdHJhdsOpcyBkZSBsYSBmdW5jacOzbiBgbW9kZWxgKS4NCg0KYGBge3J9DQpmaXQgPC0gbGF4X3Bhc3NlbmdlcnMgJT4lIA0KICBtb2RlbCgNCiAgICBQcm9waGV0ICAgICAgICA9IHByb3BoZXQocGFzc2VuZ2VycyB+IGdyb3d0aCgibGluZWFyIikgKyBzZWFzb24oInllYXIiLCB0eXBlID0gIm11bHRpcGxpY2F0aXZlIikpLA0KICAgIGBQcm9waGV0IGF1dG9gID0gcHJvcGhldChwYXNzZW5nZXJzKSwNCiAgICBBUklNQSAgICAgICAgICA9IEFSSU1BKHBhc3NlbmdlcnMpLA0KICAgIEVUUyAgICAgICAgICAgID0gRVRTKHBhc3NlbmdlcnMpLA0KICAgIEhhcm1vbmljICAgICAgID0gQVJJTUEocGFzc2VuZ2VycyB+IGZvdXJpZXIoSyA9IDMpICsgUERRKDAsMCwwKSksDQogICAgU05BSVZFICAgICAgICAgPSBTTkFJVkUocGFzc2VuZ2VycykNCiAgKQ0KZml0DQpgYGANCg0KIyMgQ29tcG9uZW50ZXMNCg0KSWd1YWwgcXVlIGNvbiBsb3MgbW9kZWxvcyBkZSBkZXNjb21wb3NpY2nDs24gdmlzdG9zIGFudGVyaW9ybWVudGUsIHBvZGVtb3MgdXRpbGl6YXIgYGNvbXBvbmVudHMoKWAgcGFyYSBleHRyYWVyIGxvcyBjb21wb25lbnRlcyBkZSBsYSBzZXJpZS4NCg0KYGBge3J9DQpmaXQgJT4lIA0KICBzZWxlY3QoUHJvcGhldCwgYFByb3BoZXQgYXV0b2ApICU+JSANCiAgY29tcG9uZW50cygpDQpgYGANCg0KYGBge3J9DQpmaXQgJT4lIA0KICBzZWxlY3QoUHJvcGhldCwgYFByb3BoZXQgYXV0b2ApICU+JQ0KICBjb21wb25lbnRzKCkgJT4lIA0KICBhdXRvcGxvdCgpDQpgYGANCkNvbiANCg0KYGBge3J9DQpmaXQgJT4lIA0KICBzZWxlY3QoUHJvcGhldCkgJT4lDQogIGNvbXBvbmVudHMoKSAlPiUNCiAgZ2dwbG90KGFlcygNCiAgICAjIFBsb3QgdGhlIG1vbnRoIG9mIHRoZSB0aW1lIGluZGV4IChtb250aCkgb24gdGhlIHgtYXhpcw0KICAgIHggPSBtb250aChtb250aCwgbGFiZWwgPSBUUlVFKSwNCiAgICAjIFBsb3QgdGhlIGFubnVhbCBzZWFzb25hbCB0ZXJtICh5ZWFyKSBvbiB0aGUgeS1heGlzDQogICAgeSA9IHllYXIsIA0KICAgICMgQ29sb3VyIGJ5IHRoZSBwYXNzZW5nZXIgdHlwZQ0KICAgIGNvbG91ciA9IHR5cGUsDQogICAgIyBEcmF3IHNlcGFyYXRlIGxpbmVzIGZvciBlYWNoIHR5cGUgYW5kIHllYXINCiAgICBncm91cCA9IGludGVyYWN0aW9uKHR5cGUsIHllYXIobW9udGgpKQ0KICApKSArICANCiAgZ2VvbV9saW5lKCkNCmBgYA0KDQojIyBQcm9uw7NzdGljbw0KDQpFcyBleGFjdGFtZW50ZSBlbCBtaXNtbyBwcm9jZWRpbWllbnRvIHF1ZSBhbnRlcyBwYXJhIGdlbmVyYXIgcHJvbsOzc3RpY29zIHBhcmEgZXN0b3MgbW9kZWxvcy4NCg0KYGBge3J9DQpmYyA8LSBmaXQgJT4lIA0KICBmb3JlY2FzdChoID0gIjMgeWVhcnMiKQ0KZmMNCmBgYA0KDQpgYGB7cn0NCmZjICU+JSANCiAgYXV0b3Bsb3QobGF4X3Bhc3NlbmdlcnMgJT4lIGZpbHRlcl9pbmRleCgiMjAxNSBqYW4uIiB+IC4pLCBsZXZlbCA9IE5VTEwpDQoNCnAgPC0gZmMgJT4lIA0KICBnZ3Bsb3QoYWVzKHggPSBtb250aCwgeSA9IC5tZWFuKSkgKw0KICBnZW9tX2xpbmUoYWVzKGNvbG9yID0gLm1vZGVsKSkgKyANCiAgZ2VvbV9saW5lKGRhdGEgPSBsYXhfcGFzc2VuZ2VycywgYWVzKHkgPSBwYXNzZW5nZXJzKSkgKw0KICBmYWNldF93cmFwKH4gdHlwZSwgbmNvbCA9IDEsIHNjYWxlcyA9ICJmcmVlX3kiKQ0KZ2dwbG90bHkocCkNCmBgYA0KDQpPdHJhIG1hbmVyYSBkZSBncmFmaWNhcmxvOg0KDQpgYGB7cn0NCmxheF9wYXNzZW5nZXJzICU+JSANCiAgYXV0b3Bsb3QocGFzc2VuZ2VycykgKw0KICBhdXRvbGF5ZXIoZmMsIGxldmVsID0gTlVMTCkgKyANCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gInRvcCIpDQpgYGANCg0KRWwgZGVzZW1wZcOxbyBkZWwgbW9kZWxvIHNlIHB1ZWRlIHJldmlzYXIgZGUgaWd1YWwgbWFuZXJhIGNvbiBgYWNjdXJhY3koKWA6DQoNCmBgYHtyfQ0KYWNjdXJhY3koZml0KSAlPiUgDQogIGFycmFuZ2UodHlwZSwgUk1TRSkNCmBgYA0KDQoNCg0KIyBDYWbDqXMNCg0KYGBge3J9DQpjYWZlIDwtIHRzaWJibGVkYXRhOjphdXNfcmV0YWlsICU+JSANCiAgZmlsdGVyKEluZHVzdHJ5ID09ICJDYWZlcywgcmVzdGF1cmFudHMgYW5kIGNhdGVyaW5nIHNlcnZpY2VzIikNCmNhZmUNCnAgPC0gY2FmZSAlPiUgDQogIGdncGxvdChhZXMoeCA9IE1vbnRoLCB5ID0gVHVybm92ZXIsIGNvbG9yID0gU3RhdGUpKSArDQogIGdlb21fbGluZSgpDQpnZ3Bsb3RseShwLCB3aWR0aCA9IDgwMCwgaGVpZ2h0ID0gNjAwKQ0KYGBgDQoNCg0KYGBge3J9DQpmaXQgPC0gY2FmZSAlPiUgDQogIG1vZGVsKA0KICAgIHByb3BoZXQgPSBwcm9waGV0KFR1cm5vdmVyIH4gc2Vhc29uKCJ5ZWFyIiwgNCwgdHlwZSA9ICJtdWx0aXBsaWNhdGl2ZSIpKQ0KICApDQpmaXQNCmBgYA0KDQpgYGB7cn0NCmNvbXBvbmVudHMoZml0KQ0KYGBgDQoNCmBgYHtyfQ0KZml0ICU+JSANCiAgY29tcG9uZW50cygpICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gTW9udGgsIHkgPSB0cmVuZCwgY29sb3IgPSBTdGF0ZSkpICsNCiAgZ2VvbV9saW5lKHNpemUgPSAxKQ0KDQojIGZpdCAlPiUgDQojICAgY29tcG9uZW50cygpICU+JSANCiMgICBnZ3Bsb3QoYWVzKHggPSBNb250aCwgeSA9IHllYXIsIGNvbG9yID0gU3RhdGUpKSArDQojICAgZ2VvbV9saW5lKHNpemUgPSAxKQ0KYGBgDQoNCmBgYHtyfQ0KZmMgPC0gZml0ICU+JSANCiAgZm9yZWNhc3QoaCA9IDI0KQ0KZmMNCmBgYA0KDQpgYGB7cn0NCmNhZmUgJT4lIA0KICBzZWxlY3QoLUluZHVzdHJ5KSAlPiUgDQphdXRvcGxvdChUdXJub3ZlcikgKw0KICBhdXRvbGF5ZXIoZmMpICsgDQogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJib3R0b20iKSANCmBgYA0KDQpgYGB7cn0NCmFjY3VyYWN5KGZpdCkNCmBgYA0KDQoNCg0KDQoNCg0KDQoNCg0KDQo=