Submission #1029791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029791		vjudge1	Addk (eJOI21_addk)	C++17	0 / 100	1557 ms	3152 KiB

Main

/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⣤⣶⣶⣶⣶⠦⠶⡶⢦⠤⠤⠤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣠⣴⣶⣿⣿⣿⣿⣿⣿⣽⣽⣿⣿⣿⣿⣿⣭⣽⣭⣯⡭⡈⢙⣽⣶⣤⣤⣄⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣶⣟⣟⣽⣾⣿⢿⣿⡿⣿⣿⣿⣿⣿⣿⣟⠟⡻⣿⣿⣟⣟⣟⣿⡻⠿⠿⠿⠿⣍⠉⠉⠉⠙⠛⠛⠒⠒⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣶⣿⣿⣿⣿⡿⣾⣿⣯⣿⣿⣿⣽⣿⣷⣽⣿⣿⡿⣿⣿⣾⢿⣿⡷⣿⣿⣿⣿⣯⣭⡅⣠⣹⣢⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⡿⣿⣟⣽⣿⣿⣿⣻⣿⣟⣟⣿⣻⣿⣝⣿⣯⣿⣻⣻⣿⣿⣿⣿⡪⡻⣿⣿⣽⣿⣿⣯⣻⣿⣶⣿⣖⣓⡤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠿⢿⣿⣟⣿⣿⣻⣿⣿⣿⠿⣿⣿⡿⣿⣿⢿⣿⡯⣿⣛⣿⣕⣿⣿⡿⣿⣿⣷⢿⡿⣻⣿⣿⣿⢿⣿⣿⡻⣿⡷⠷⠯⠦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡽⠹⠩⡝⡇⡿⢻⢻⢻⡛⣿⣹⣿⣿⣿⣿⣿⣽⣿⣯⣿⣿⣿⡿⣿⣿⣿⣿⣽⡿⣿⣯⣻⣿⣿⡿⣿⣿⣿⣿⣿⣝⡍⠩⠀⢘⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣏⣓⣂⣀⣀⠀⣜⣀⣀⠐⠐⠓⣞⠨⣿⠿⣗⣿⣿⣻⣿⣿⣽⣿⣿⣺⣿⣿⣿⣿⣻⣿⣿⣿⣝⢿⣛⠻⣻⣿⣟⣟⣿⣿⣿⣤⣐⣒⣚⣳⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⠟⠻⠽⢯⣌⣶⣿⠿⡡⢴⣾⠛⢀⣷⡉⡟⣷⢊⢘⢀⡙⣷⣾⣿⣿⣿⣿⣿⣿⢿⣿⢿⣿⡿⣿⣿⣽⢋⣝⣿⡿⣿⢿⢿⣛⢿⣿⣗⢇⠟⢦⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⣿⣿⣉⣉⣉⣸⣿⣿⣉⣉⢉⣿⠷⠶⠀⢸⣿⣿⢿⠀⠀⠀⠀⢸⠀⢀⡷⣿⣿⣿⢿⡿⡇⣿⣉⢾⣿⣿⠰⢶⡶⣿⣿⣿⣿⣹⣿⡀⠹⣿⣿⡹⣉⢷⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⡭⣥⣿⣾⣿⣿⣿⣿⣿⣿⣓⡃⠐⠀⣘⣯⣿⣚⣟⢒⣓⣒⣿⣒⢺⣟⣻⡧⡉⣿⡿⠍⡭⢭⠨⠹⢿⣝⢒⡞⠀⡖⣚⢷⣙⢛⣯⣦⠈⠻⢿⣿⣮⣧⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⢩⣿⣿⣿⣾⣷⣿⣿⣿⣟⠒⠀⠐⠀⠉⡿⡟⠉⠹⣿⣟⣳⣶⣆⣴⠑⠀⢳⡄⠈⣷⡁⠁⠈⠀⢈⠙⣷⠀⣀⣀⣀⠀⢨⣷⠀⠊⣟⢣⠀⠀⠉⠛⠿⣿⣄⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣗⡺⣿⣿⣿⣿⣿⣿⣿⡿⡏⠍⠁⢈⠀⠉⠁⣷⠩⠩⠨⢿⣷⣿⣿⡟⠀⠈⠅⠽⣹⣯⡵⣖⣶⣶⣶⡖⣿⡬⢭⡭⣽⣿⠭⣿⡠⠥⣼⣷⢧⠀⠀⠀⠀⠀⠙⠳⢄⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⡏⡃⢀⣠⣬⣶⣶⣦⣍⢀⠈⢸⣘⣧⣿⣿⣏⠀⣀⠀⣃⣷⢿⣼⣽⣆⡲⡦⢵⣾⣿⠃⣧⣿⣿⡼⣿⣿⣇⣻⣿⣘⡆⠀⠀⠀⠀⠀⠀⠈⠛
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢦⣾⠟⠻⠹⢰⣶⣆⡚⢷⡀⠠⠶⡞⣾⣿⠤⠀⠠⡀⢒⡞⠻⣷⠐⢻⣿⣮⡕⣷⣿⡖⣿⣿⣿⡏⣽⣿⣿⢶⣿⣿⢾⡄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣽⣿⣿⡯⡿⢿⢽⣽⣮⣯⣯⡟⠬⠅⢡⡀⣠⣽⣿⣧⠵⠁⠀⠀⠇⡍⢿⠀⠀⠤⠀⠏⠩⠬⠹⡤⠀⣿⢝⡿⡯⣾⣯⣿⣟⣯⣖⣺⣿⣕⠽⣯⣿⣬⣽⡀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣻⣿⣿⠷⠿⠿⣻⣿⣟⣿⣿⠆⠁⢠⣿⣿⡽⠿⡿⣿⠀⠀⠀⠀⠀⠉⠋⠀⠀⠀⠀⠒⠉⠊⢈⠋⠁⡋⣻⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣷⣿⣿⣟⣹⣿⡆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⡿⣿⣿⣿⣿⡭⢹⣿⣿⣻⣽⣿⡀⠀⢨⡇⠉⠍⢌⠼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠴⣶⢶⠾⢦⣆⠂⠚⣿⣷⣽⡗⣿⡯⣿⠵⢿⣯⣯⣿⣿⣿⣕⣯⣇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣯⣿⣗⣿⣿⣿⡓⣒⣛⣽⣿⣿⢿⣯⠥⠀⠈⢶⡂⠐⣾⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠉⢙⣿⣌⣮⠽⣿⣍⢯⣻⣻⣯⠭⠥⣯⠬⣿⣿⣿⣟⣿⣻⣾⣏⢹⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣾⣿⣷⣿⣿⡇⡇⠴⣹⣿⣿⣾⣉⢹⣄⡀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⣠⡄⠀⠀⠀⠀⣀⣷⣶⣾⣿⣿⠈⠀⡉⣿⢙⣏⢾⣏⡉⡁⡁⣹⣿⣿⣳⣷⣿⣿⢞⣾⡌⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣯⣿⣿⣿⣿⣭⠭⢭⣿⣿⣷⡒⢀⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡿⠇⠀⠀⠀⠰⡟⣿⢨⠽⢕⡟⠀⠂⣲⡟⠒⢺⣽⣷⣾⡶⠒⣺⣿⣯⣿⣿⣾⢽⣝⣿⠆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣟⣿⣿⣿⣧⣚⣾⣚⣿⣿⠬⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠋⠀⠀⠀⠀⠐⣇⠈⢐⢰⡏⠁⠠⢠⡿⠤⣤⣿⣻⣟⣿⠥⣾⣿⣿⣿⣿⣿⣿⡾⡳⣿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡷⣿⣿⣿⣿⡿⣽⣿⢿⣿⣿⠶⠾⣿⣿⢉⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠒⠒⠛⠀⠤⠾⣛⣀⣽⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣯⣿⣿⣿⣿⣫⣫⣿⣿⢕⣿⣭⢹⡿⣿⣷⣐⣀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⣢⣫⣿⣿⣟⣿⣿⣾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣷⢿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⢟⢟⣿⣿⣷⡿⣟⢄⣻⡻⣿⣷⡬⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣾⣛⣿⣿⡿⣿⣿⣟⢟⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡿⣿⣿⣿⡗⣽⣿⣿⣿⣿⣕⡽⣍⢯⣿⣿⣿⢅⠠⠀⠀⠀⠀⠉⠙⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣬⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⡵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡽⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⢸⣿⣿⠇⢸⣿⣿⣯⣺⣿⣿⣿⣿⣿⣿⣦⢟⣿⣯⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣾⣿⣿⣿⣿⣿⣿⣗⣟⣿⣿⣺⡯⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣺⡆⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣤⣶⣾⣷⣿⣿⣯⣳⡤⣀⣿⡏⠀⢸⣿⣿⣿⣾⠯⣿⣿⣿⣿⣿⣿⣿⢷⣿⣩⠨⠽⡿⣷⣄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣠⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⢏⣀⣻⣿⣿⣿⣿⣿⣿⣿⣾⡿⣿⣯⢿⡀⠀⠀⠀
⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣟⣖⢤⣘⣿⣿⣿⣷⣽⣿⣿⣿⣿⣿⣿⣷⣗⣭⡿⣬⣭⡯⣭⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣺⣿⣿⣿⣕⢒⣿⣿⣿⣿⣿⣿⣿⣿⣻⣾⡿⣿⣿⣇⠀⠀⠀
⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣝⢻⡻⣿⣟⣿⢟⡿⣿⣾⣿⣷⣟⢶⠐⢐⣰⣇⣲⣗⣾⢐⣐⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢽⣟⢽⣿⡺⢩⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡯⡾⣿⢽⡄⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣾⡻⣷⣿⣟⢿⣿⣿⣿⣿⢷⡤⠀⠴⠑⠷⠶⠰⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣻⢿⣿⣿⣿⣿⣿⣿⣿⣻⣿⣯⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⢟⢟⢿⣿⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣝⣿⣿⣝⣿⣿⣿⣿⣷⣽⣄⠄⠀⠄⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢝⣿⡆⠙⠿⣿⣿⣿⣿⣺⣺⠟⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣟⢽⠈⢿⡆⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢾⣿⣿⣿⣿⣿⣾⣇⡀⠆⢀⣿⣿⣷⣿⣿⣿⣿⢿⣿⠁⠈⣿⣿⣿⢾⡇⠀⠀⠀⠹⣿⡿⣿⣉⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣏⢾⠀⠀⣇⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣿⣿⣿⣿⣿⣿⣮⡶⣤⣿⣿⣿⣿⣿⣿⣿⡿⣿⡗⠀⠀⠀⠙⢿⣿⣻⠀⠀⠀⠀⠈⣿⡿⣶⣾⣽⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⡏⠀⠀⣼⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢽⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣵⢝⢵⣿⡯⣯⠃⠀⠀⠀⠀⠀⠙⢿⡄⠀⠀⠀⢰⣿⠗⠉⠙⠿⣮⣧⡈⠻⣿⣿⣿⣿⣿⣿⣿⡯⣮⡇⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣫⣿⣿⣿⣿⣷⣿⣿⣿⣾⣾⣻⣻⣿⣻⣟⢿⣶⣄⡀⠀⠀⠀⠀⠀⠓⠀⠀⢠⡿⠁⠀⠀⠀⠀⠈⠙⠻⢦⠈⠿⣿⣿⣿⣿⣿⣟⣿⠁⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣾⣾⣿⣿⣿⣿⣾⣿⣿⣷⣽⣾⡿⣷⣤⣀⠀⠀⠀⠀⠀⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠓⠀⠈⠻⣿⣿⣿⣷⡏⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⡿⣿⣷⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⡟⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣾⡿⣷⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⠃⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢯⣿⣯⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣯⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠋⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⠋⠀
*/
// skibidi rizz
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
// #define endl "\n"
#define int ll
#define F first     
#define S second
#define db double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
using namespace std;
const   ll inf = 1e18,MOD=998244353,N=3e5+10,MN=1e9+7,lim=1e6;
const long db Phi=acos(-1);
ll binpow(int a,int p);
void solve(){
  int n,k;
  cin>>n>>k;
  vector<int>v(n+1);
  for(int i=1;i<=n;i++){
    cin>>v[i];
  }
  int q;
  cin>>q;
  while(q--){
    int type;
    cin>>type;
    if(type==1){
      for(int i=0;i<k;i++){
        int a;
        cin>>a;
        
      }
    }
    else{
      int l,r,m;
      cin>>l>>r>>m;
      int ans=0;
      for(int i=l;i<=r;i++){
        int mn=inf;
        if(i<l+m){
          mn=min(mn,v[i]*(i-l+1));
        }
        if(i>r-m){
          mn=min(mn,v[i]*(r-i+1));
        }
        mn=min(mn,v[i]*m);
        ans+=mn;
        // cout<<
      }
      cout<<ans<<endl;
    }
  }
 }       
signed main() {
    srand(time(NULL));
    IOS;
    //freopen("coins.in", "r", stdin);
    //freopen("coins.out", "w", stdout);
    int UwU=1;
    // cin>>UwU;
    for(int i=1;i<=UwU;i++) { 
      // cout<<"Case "<<i<<": ";
        solve();
      // cout<<endl;
    }
}
ll binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8