fork download 
  1. /**
  2. *    Author : M1nK
  3. *    Device : Laptop
  4. *    Created : 06.07.2025
  5. *    Problem : https://o...content-available-to-author-only...i.info/problem/bedao_r09_treetravel
  6. **/
  7.  
  8. /*
  9.  
  10.                                                                                                 ▒███████▓▒░
  11.                                                                                              ███▓░░░░░░░████▓
  12.                                                                                            ░██░░░░░░░░███▓ ░▒
  13.                                                        ██████████████████████████          ██░░░░░░░██▓▓█████▒
  14.                                                  ███████░░░░░░░███░░░░░░░░░░░░░░░███▓    ▓███░░░░░████▒░░░▒████
  15.                                      █████████████░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░████████▓▓██░░░███░░░░░░░░░░██░
  16.                                      ▒██░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░░░░░░░░▓██████▓▓▓▓██░██▓░░░░░░░░░░░░▒█
  17.                                       ░███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▓▓▓▓██▓███████▓████████░░░░░░█▓
  18.                                          ███▓░░░░░░██░░░░░░░█░░░░░░░░░░░░░█▓░░░░░▒█▓▓▓▓▓▓██▓▓███▓▓▓█▓    ███░░░██▒
  19.                                            █▓░░░░██░░░░░░░░█▓░░░░░░░░░░░░░░█▓░░░░░░███▓▓▓██▓▓▓▓▓▓▓██      ░█▓░███
  20.                                          ▒█▒░░░██░░░░░░░░░██░░░░░░░░░░░░░░▓██▓░░░░░░▒█████████▓▓▓███      ▓████░
  21.                                         ░█▒░░░██░░░░░░░░░░██░░░░░░░░░░░░░░████░░░░░░░░░░▒█████████░▓█     ███
  22.                                         ██░░░██░░░░░░░░░░▒█▒░░░░░░░░░░░░░██░▓██░░░░░░░░░░░░░░░░█▓░░░█▓
  23.                                        ▒█▒░░░█▒░░░░░░░░░░▒█▒░░░░░░░░░░░░▓██░░▒██░░░░░░░░░░░░░░░░░░░░▒█░
  24.                                        ██░░░███░░░░░░░░░░██▒░░░░░░░░░░░▒██░░░░░██░░░░░░░░░░░░░░░░░░░░██
  25.                                       ██░░░▒███░░░░░░░░████▓░░░░░░█░░░▒██▒░░░░░░██░░░░░░░░█▒▒██░░░░░░██▓
  26.                                      ██░░░░████░░░░░░██▓  ██░░░░░██░░▒██░█▒░░░░░░██░░░░░░░██▒▒██░░░░░░██░
  27.                                     ██░░░░██░▒██░░░░█▓    ▒█▒░░░███░▓█▒  ▓█░░░░░░▒█▒░░░░░░▒██░░██░░░░░░██░
  28.                                   ░█▒░░░░██░░░███▒▒█▒      ▓█░░░█████░    ▓██░░░░░██░░░░░░░██░░░██░░░░░░████▒    ▓
  29.                                  ██░░░░░██▒░░▓█░████        ▓█▓▒█░█▓       ░██▓░░░░██░░░░░░▓█▓░░▒██▓░░░░░░░▓██████
  30.                                ░█▒░░░░░██▓░░██               ░███ ░          ▒███░░██░░░░░░▒██░░░████▓░░░░░░▒██▓
  31.                               ███████████░▒█▒  ██                               ▒████▒░░░░░▒██░░░░██▒▓██████▓
  32.                                       ██░██░                                        ██░░░░░███░░░░▒██░░██
  33.                                      ▒█▓▒█░                                         ▓█░░░░▒██▓░░░░░██▓░░█▒
  34.                                      ██░█▓                                     ██   ▓▓░░░▒███▒░░░░░▒██░░█▓
  35.                                      ██░▒█              ██████████████              █▒░░█████░░░░░░░██░░█▒
  36.                                      ██░░██             █▓▓▓▓▓▓▓▓▓▓▓██             ░█░▓██▓██▓░░░░░░░██░░█▒
  37.                                      ██░████░            ██▓▓▓▓▓▓▓▓██              █████ ░██░░░░░░░███░░█░
  38.                                      ██████▓██             █▓▓▓▓▓▓██              ▓█▓░  ▒█▓░░░░░░░░██░░░█░
  39.                                       ███ ██░░██░            █████                    ░██░░░░░░░░░██▒░░░█░
  40.                                           ██░░░░███░                              ░░██▓░░░░░░░░░░██▒░░░░█░
  41.                                            ██░░▓░░░███▓░                       ▒███▓░░░░░░░░░░░███░░░░░░█▒
  42.                                             ██████▓░░░▒████▓░                   ░█▓░░░░░░░░░░██▓ ██▓░░░░▒█
  43.                                              ▓██ ░████████████████▓▓░░░░░░░░░░▒██████▓▒▒▒▓██▓     ▒███▒░░██
  44.                                                ▒ ▒█████░ ▓█▓▓▓▓███▓████████████░░░▒█████░░▒█▒         ▒████
  45.                                               ▒▓████▓    ▒█▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓█       ▓███████
  46.                                               ▓███▓▓▓▓   ░█▓▓▓▓███▓▓▓▓▓▓▓▓▓▓██      ▓▓▓▓▓████▓
  47.                                            ░████░███▓▓▓█▓  ░████▓██▓██████████▓▒  ░▓▓▓▓████▓██▓
  48.                                           ░███    ░█████   ██▓▓██▓▓▒███▓███▒   ███░▓▓▓▓███░▒████▒
  49.                                        ▒██▒░██   ██████     ███   ▓▓  ░█████    ░████████░ ░██░▓▓█▒                    ░██
  50.                         ███████████████▒░░░░▒█░  ██░░░█░          ▒▓            ▓█░░░▒█░   ██░░▒▓████▓▓░               ████
  51.                          █▒░░░░░░░██▒░░░░░░░▒█░  ▒█▒░████▓▓▓▓█████████▒       ▓████▓██░   ██▓░░▓▓░░▒▓▓███░           ███░▒██
  52.                          ░██░░▒██▓░░░░░░░░░░▓██  ░██░   ░ ▒█▓▓▓▓▓▓▓▓▓▓██████████░   █▓   ██▒░░░▒▓░▒▓▓░░█████████████▓░░░░░██
  53.                             ██▓░░░░░░░░░░▒██▓ █▓ ░█░   ███████████▓▓▓▓▓███████████████▒██████░░░▓▓▓▓░░░░░░░░███▒░░░░░░░░░██
  54.                            ▓█░░░░░░░░▓██▒     ░█▓███████▓▓▓▓██████████████▓▓▓▓▓▓▓▓▓▓████▓    ▓██▓▓▓░░░░░░░░░░░░░▓██▒░░░███
  55.                            █▒░░░░░░▓██          ████▓▓▓▓▓████ ██▓▓▓▓▓▓▓█░████▓▓▓▓▓▓▓████▒      ▓▓▓▓███▒░░░░░░░░░░░▒█████▒
  56.                            █▓░░░░░██          ░███▓▓▓████▓   ██▓▓▓▓▓▓▓▓█▒  ░█████████▒ ██     ▓▓   ░▓  ███▒░░░░░░░░░███
  57.                            ██▒░░░██           █▓▓██████    ░██▓▓▓▓▓▓▓▓▓█▒    ░███████████    ░▓▓▓▓▓▓▓▒    ▒██▒░░░░░░░██
  58.                             ███░░█▓           ██▓█████████████████████████████▒ █████████                    ██░░░░░░██
  59.                               ▓█████          ████████▒                         ░████████                      █▒░░░░██
  60.                                               ░███████                           ███████▒                       █▒░░▓█
  61.                                                ██████░                            ██████                        ██░▓█▒
  62.                                                 ▒███                                ███                         ████░
  63.                                                                                                               ░████
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣀⣀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  72.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣶⣦⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  73.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣦⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  74.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⢿⣟⡿⣿⢿⡿⣿⢿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  75.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣻⣽⡾⣽⣯⢿⣾⣻⣽⣯⢿⣽⣯⢿⣳⣟⣾⡽⣯⣟⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  76.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⣟⡷⣯⣷⢯⣟⡿⣞⣿⣳⣯⣷⣻⣟⣾⣽⣻⣟⣾⣽⣻⢷⣻⣽⡷⣯⢿⣽⢿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  77.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣟⡷⣯⢿⣻⢾⣟⣯⢿⣻⢷⣯⡷⣯⣷⢿⣽⢾⡷⣯⣟⣾⢯⡿⣯⡷⣟⣿⣻⢾⣯⡷⣿⣻⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  78.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⣿⣻⣞⣿⡽⣟⣯⣿⢾⣯⢿⣯⢿⡾⣽⣟⡾⣟⣾⢿⣽⣻⢾⣯⣟⣿⣳⣿⣻⢷⣻⣯⡷⣟⣯⣷⣟⡿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  79.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣟⡾⣷⣻⣾⣻⢯⣟⣾⣟⣾⣟⣾⢿⣽⣟⡾⣟⣯⣟⡿⣞⣿⣻⢾⣽⣾⣻⢾⣽⣻⣟⣾⡽⣿⡽⣾⣽⣻⣽⢿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  80.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣟⡾⣿⡽⣷⢯⣟⡿⣽⣾⣻⢾⣽⡾⣟⣾⣽⣻⢯⣟⣾⣟⣯⣷⢿⣯⣷⣯⣟⣯⣟⣷⣯⣷⣿⣯⣟⣷⣯⣟⣾⣿⡽⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  81.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣿⣟⡾⣟⣷⢿⣯⣟⣯⣿⣻⢾⣽⣯⡷⣟⣿⣽⣞⣿⣯⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  82.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣟⡾⣟⣯⣟⡿⣾⣽⣳⣯⣟⡿⣞⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⠀⠀⠀⠀⠀⠀
  83.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣟⡾⣟⣯⢿⣞⣿⣳⣯⣟⣾⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⠛⠛⠋⠉⠉⠉⠉⠉⠉⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠉⠙⠛⠿⠿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
  84.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⡿⣞⣿⢯⣟⣯⡿⣾⣽⣳⣯⣟⣾⣿⣿⣿⣿⣿⣿⣏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠄⠒⠀⠀⠀⠀⠀⠀⠀⠀⠀⠒⠠⠄⢀⣸⠀⠈⠙⠻⣿⣿⣿⣿⣿⣧⡀⠀⠀⠀
  85.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣻⢯⣟⣯⣿⣳⡿⣽⡾⣯⡷⣿⣿⣿⣿⣿⣿⣛⢶⣻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣷⠠⡀⠀⠈⠙⣿⣿⣿⣿⣿⡄⠀⠀
  86.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣯⣟⡿⣽⣳⣯⡷⣿⢯⣟⣷⢿⣿⣿⣿⣿⣿⡳⣝⡮⡽⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠤⣠⡀⠀⣿⠀⠈⢆⠀⠀⠈⢻⣿⣿⣿⣿⡀⠀
  87.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣿⢾⣽⣻⢯⣟⣾⣽⣟⣯⡿⣾⢿⣿⣿⣿⣿⡿⣵⢫⣞⡵⣻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠢⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⣟⠉⠉⠑⡾⠶⠤⠄⠈⣿⣿⣿⣿⣧⠀
  88.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣸⣿⣿⣿⣿⣿⣯⢿⣳⣿⣻⡽⣷⣻⡾⣽⣻⣽⣿⣿⣿⣿⣿⡿⣜⣳⢎⡷⣝⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠁⠐⠠⠄⢀⡀⠀⠀⠀⠀⠀⡇⣀⠀⠤⠊⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⡄
  89.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣴⣶⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢾⣻⣟⣾⣽⣻⣽⢷⣟⡿⣽⣞⣿⣿⣿⣿⣿⡿⣜⢧⡻⣜⡳⣞⢷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⡇⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⡇
  90.         ⠀⠀⠀⠀⠀⢀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣟⡿⣾⣽⣞⣯⣟⡿⣾⣻⣽⡾⣿⣿⣿⣿⣿⣿⡹⢮⣝⢧⡟⣼⢫⡽⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣶⣿⣿⣿⣿⣿
  91.         ⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⢿⣿⣿⣿⣿⣿⣿⣳⡿⣽⣷⣻⢾⣻⢾⣻⡷⣟⡷⣿⣽⣿⣿⣿⣿⣿⣝⡳⢮⣳⠽⣎⠿⣼⡹⢷⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⠀⠀⠀⠀⣀⣀⣤⢶⡞⣯⢳⢧⣿⣿⣿⣿
  92.         ⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⡿⣟⡿⣽⣯⢷⣯⢿⣽⣻⣿⣿⣿⣿⣿⣟⡷⣿⣻⢾⣽⣟⣯⡿⣷⣟⡿⣽⡷⣯⣿⣿⣿⣿⣿⣾⣹⢳⣭⣛⢾⡹⣖⢯⣳⢎⡟⣿⢲⡶⢶⢶⣤⣤⣤⡤⣤⣄⡤⣤⢤⡤⣤⢤⡖⣶⢲⡖⣿⢻⡽⣹⢎⡷⣹⢞⡽⢮⣿
  93.         ⠀⠀⠀⣼⣿⣿⣿⣿⣿⢯⣟⡿⣽⣟⡾⣿⡽⣯⡿⣽⣿⣿⣿⣿⣿⣯⢿⣷⣻⣯⣷⢯⡿⣽⡷⣯⢿⣯⣟⣷⢿⣿⣿⣿⣿⣿⣮⢗⡮⣝⡮⢷⣹⢎⡷⣫⢾⡱⣏⠾⣝⠾⣜⡶⣣⢟⡶⣹⢞⡵⣫⢞⡵⣫⢾⡱⣏⡾⣱⣏⠾⣵⢻⡜⣯⢞⡽⣻⣿
  94.         ⠀⠀⢰⣿⣿⣿⣿⣿⣯⢿⣯⣟⡿⣞⣿⣳⡿⣯⣟⣿⣿⣿⣿⣿⣿⢯⣿⣞⣷⣟⡾⣿⡽⣷⣟⣿⣻⢾⣽⣾⣻⢿⣿⣿⣿⣿⣿⣿⣼⢣⡟⣧⣛⢮⢷⡹⣎⢷⣫⢟⣮⢻⡵⣫⢗⡯⣞⡵⣫⡞⣵⣛⢾⡱⣏⢷⡹⣞⡵⣚⠿⣜⣧⢻⡜⣯⣾⣿⣿⠀
  95.         ⠀⠀⣾⣿⣿⣿⣿⡿⣽⣻⡾⣽⣻⣯⡷⣿⡽⣷⣻⢿⣿⣿⣿⣿⣿⢯⣷⢿⡾⣽⣻⢷⣟⡿⣞⣷⢿⣯⡷⣯⣟⣯⣿⣿⣿⣿⣿⣿⣿⣿⣾⣵⣫⡞⣧⢻⡝⣮⢳⣏⡞⣧⢻⡵⣫⢞⡵⣫⢷⡹⢮⣝⡮⣽⢺⣭⢳⡝⡾⣭⣛⠾⣜⡧⣟⣿⣿⣿⣿
  96.         ⠀⢰⣿⣿⣿⣿⣿⣟⣯⣷⢿⣻⢷⣯⢿⣳⡿⣯⣟⣿⣿⣿⣿⣿⡿⣯⣟⣯⣿⣻⡽⣿⣞⡿⣯⣟⡿⣾⡽⣟⣾⣻⢾⡽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣼⣷⣮⣝⣞⣧⡻⣵⢫⢾⡱⢯⣝⡳⢮⣳⢭⡗⣮⢻⣼⣳⣧⣯⣿⣾⣿⣿⣿⣿⣿⣿⠀⠀
  97.         ⠀⣸⣿⣿⣿⣿⣿⣞⡿⣾⣻⢯⣿⢾⣟⣯⢿⣷⣻⣿⣿⣿⣿⣿⣿⣽⢾⣻⡾⣽⣻⢷⣻⣽⣟⡾⣟⣷⢿⣻⢷⣻⣯⢿⣳⣯⢿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀
  98.         ⠀⣿⣿⣿⣿⣿⣟⣾⣟⡷⣿⣻⡽⣟⣾⢯⣿⣞⡿⣿⣿⣿⣿⣿⡷⣯⡿⣯⣟⡿⣽⣻⢯⣷⣻⣽⢿⣾⣻⢯⣿⣻⢾⣟⣯⣟⣯⡿⣯⣟⡿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀
  99.         ⢰⣿⣿⣿⣿⣿⣟⣾⣽⣻⢷⣟⡿⣯⣟⣯⣷⣟⣿⣿⣿⣿⣿⣿⣟⡷⣿⡽⣯⣟⡿⣽⣻⢷⣻⡽⣟⣾⡽⣟⣷⣻⣟⣾⣻⡾⣽⣻⢷⣻⣽⢯⣿⢾⡽⣯⣟⣿⣻⣟⡿⣿⢿⡿⣿⢿⡿⣿⣿⣿⣿⣿⣿⣿⣿⢿⡿⣿⢿⣿⣻⢿⡽⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀
  100.         ⢸⣿⣿⣿⣿⣿⣻⣞⣷⢿⣻⡾⣿⣽⢾⣻⡾⣽⣾⣿⣿⣿⣿⣿⣯⢿⡷⣟⣯⡿⣽⢿⣽⣻⢯⣟⡿⣽⣻⢯⣟⣷⢯⣟⡷⣿⣻⡽⣟⣯⣟⣯⣟⣯⣿⣽⢾⣳⡿⣞⣿⡽⣯⣿⣽⣻⣽⣷⣻⣞⣷⣻⣞⣷⢯⣟⣿⡽⣟⣾⡽⣟⣿⣿⣿⣿⣿⡗⠀⠀⠀⠀⠀
  101.         ⢸⣿⣿⣿⣿⣿⣳⣯⣟⣯⡿⣽⡷⣯⡿⣯⣟⡿⣾⣿⣿⣿⣿⣿⣯⢿⣽⣟⡷⣿⣻⣟⣾⣻⢯⣟⣿⡽⣯⣿⣻⢾⣟⣯⢿⣷⣻⣽⢿⣽⢾⣻⣾⣻⢾⣽⣻⢯⣟⣯⣷⢿⣻⣞⡷⣟⣷⢯⣷⢿⣽⣳⡿⣾⣻⣟⣾⣻⢯⡿⣽⣟⣾⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀
  102.         ⢸⣿⣿⣿⣿⣿⣳⢿⣞⣯⡿⣷⣟⣯⢿⣷⣻⣟⣿⣿⣿⣿⣿⣿⡽⣿⢾⣽⣻⢷⣯⢿⣞⡿⣯⢿⣞⣿⣳⣯⣟⡿⣞⣯⣿⢾⡽⣯⡿⣾⣻⢷⣯⣟⣯⣷⢿⣻⡽⣷⢯⣿⣻⢾⣟⡿⣾⣻⡽⣟⣾⢯⣟⣷⢿⡾⣽⢯⣿⣻⣽⡾⣯⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀
  103.         ⢸⣿⣿⣿⣿⣿⡽⣯⣟⡷⣿⣳⣯⢿⣻⡾⣷⢯⣿⣿⣿⣿⣿⣿⡿⣽⣯⡷⣿⢯⣟⣯⡿⣽⣻⣯⢿⡾⣽⣳⡿⣽⢿⣽⢾⣻⣟⡷⣿⡽⣯⣿⢾⣽⣳⣯⢿⣯⣟⣯⣿⣳⢿⣻⡾⣟⣷⢿⣽⢿⣽⣻⣽⡾⣿⣽⣻⣯⡷⣟⡷⣿⣽⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀
  104.         ⢸⣿⣿⣿⣿⣿⡽⣟⣾⢿⡽⣷⣻⢿⣽⣻⣽⣟⣿⣿⣿⣿⣿⣿⣟⣷⢯⣿⣽⣻⢯⣷⢿⣻⢷⣻⣯⣟⣿⣳⢿⣯⢿⣾⣻⣟⡾⣟⣷⢿⣻⢾⣯⣟⣷⣻⣟⣾⣽⣳⣯⣟⣿⣳⡿⣯⣟⡿⣾⢯⣷⣟⡷⣿⣳⣯⡷⣿⣽⣻⣽⡷⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀
  105.         ⢸⣿⣿⣿⣿⣿⣽⣻⣽⣯⢿⣯⣟⣯⣷⣟⡷⣯⣿⣿⣿⣿⣿⣿⣻⢾⣟⡷⣯⣟⡿⣽⣻⢯⣿⣻⢾⣽⣾⣻⣟⣾⣟⡷⣟⣾⣟⣯⣟⣯⣿⣻⢾⣽⣾⣻⢾⣽⡾⣯⡷⣿⢾⣽⣻⢷⣻⣽⣯⢿⣳⣯⢿⣷⣻⢷⣻⡷⣯⣟⣾⣽⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
  106.         ⢸⣿⣿⣿⣿⣿⢾⣽⣳⣯⣿⢾⣽⣳⡿⣞⣿⣽⣻⣿⣿⣿⣿⣿⣟⡿⣾⣻⣽⢯⣿⣻⣽⣟⣷⣻⣯⡷⣯⣷⣻⢷⣯⢿⣻⢷⣯⣟⣾⣻⢾⡽⣟⣷⢯⣟⣯⣷⢿⣳⡿⣯⣟⡷⣿⣻⢯⣷⣻⢿⣽⡾⣟⣾⢯⡿⣯⣟⣷⢿⣽⡾⣽⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
  107.         ⢸⣿⣿⣿⣿⣿⢯⣟⡷⣟⣾⢿⣽⣳⣿⣻⢷⣯⣿⣿⣿⣿⣿⣿⣯⣟⣷⢿⣽⣻⢷⣯⡷⣿⣞⡿⣾⣽⢷⣻⣽⣟⣾⣟⣯⡿⣾⣽⣳⡿⣯⢿⣻⡾⣿⣽⣻⢾⣻⣽⣻⢷⣻⣟⡷⣿⢯⣷⢿⣻⣾⡽⣿⣽⣻⣽⣷⣻⡾⣟⣾⣽⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀
  108.         ⢸⣿⣿⣿⣿⣿⣯⢿⣽⢿⣽⣻⡾⣟⣾⡽⣿⢾⣽⣿⣿⣿⣿⣿⣷⣻⡾⣿⡽⣯⣿⣞⣿⣳⡿⣽⡷⣯⣿⣻⢾⣽⡾⣽⣾⣻⢷⣯⢿⣽⣻⢿⣽⣻⢷⣯⣟⡿⣽⣳⣿⣻⣽⡾⣿⡽⣟⣾⢿⣽⣞⣿⣳⣯⣟⣾⣳⡿⣽⣻⣽⡿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀
  109.         ⠸⣿⣿⣿⣿⣿⡾⣿⣽⣻⡾⣯⣟⣯⣷⢿⣯⣟⣿⣿⣿⣿⣿⣿⣷⣻⣽⢷⣟⡿⣾⣽⢾⣯⢿⣽⣻⢷⣯⣟⣯⣷⢿⣻⡾⣽⣟⣾⣟⡷⣿⢯⣷⣟⡿⣾⣽⣻⢯⣟⣾⣽⣳⣿⣳⢿⣻⡽⣟⣾⣽⢾⣻⡾⣽⣳⡿⣽⣻⣽⡿⣽⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀
  110.         ⠀⣿⣿⣿⣿⣿⣟⣷⢯⣷⢿⣯⣟⡷⣯⣿⢾⣽⣾⣿⣿⣿⣿⣿⡷⣯⣟⡿⣾⣻⢷⣯⡿⣾⣻⣽⢯⣿⢾⣽⣳⣯⣿⣳⣿⣻⢾⣳⣯⢿⣯⢿⡾⣽⣻⢷⣯⣟⡿⣽⣳⣯⣷⢯⣟⡿⣽⣻⢯⣟⣾⣟⡷⣿⣻⣽⣻⣽⣿⢯⣟⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀
  111.         ⠀⣿⣿⣿⣿⣿⣟⣾⢿⣽⣻⡾⣽⣻⣽⡾⣟⣷⢯⣿⣿⣿⣿⣿⡿⣽⡾⣟⣷⢿⣯⡷⣟⣯⡿⣾⣻⣽⣯⣟⡷⣟⣾⣽⣞⣯⡿⣯⣟⡿⣾⣻⣽⢿⣽⣻⡾⣽⣻⢯⣟⣾⣽⣻⡽⣟⣯⢿⣻⣽⡾⣯⣟⣷⣟⣷⣿⣻⡾⣟⣯⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀
  112.         ⠀⢸⣿⣿⣿⣿⣿⣽⣻⡾⣯⣟⡿⣽⣳⣿⣻⢾⡿⣿⣿⣿⣿⣿⡿⣽⣻⣽⢯⣿⢾⣽⢿⣽⣻⢷⣟⣷⣻⢾⣟⡿⣽⣞⣯⣷⢿⣽⣾⣻⢷⡿⣽⣻⣞⣯⢿⣻⣽⣟⣯⣷⣻⡽⣟⣯⣿⣻⡽⣷⣻⣽⡾⣿⢾⣯⡷⣿⣽⣻⢷⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀
  113.         ⠀⢸⣿⣿⣿⣿⣿⣞⣷⢿⣯⢿⣽⢿⣽⣞⡿⣯⢿⣿⣿⣿⣿⣿⣿⣻⣽⡾⣿⣽⣻⡾⣟⣷⢿⣻⡾⣯⣟⡿⣾⣻⢯⣟⣷⣯⢿⣳⣯⣟⣯⡿⣯⣷⢿⣽⣻⣟⣾⣽⢾⣳⡿⣽⣟⡷⣯⣷⢿⣯⣟⡷⣟⣯⣿⢾⣽⡷⣯⣟⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀
  114.         ⠀⠀⣿⣿⣿⣿⣿⣟⣾⣟⣾⢿⣽⣻⣾⣽⣻⣽⣟⣿⣿⣿⣿⣿⣿⣳⣯⢿⣳⣯⣷⢿⣻⡾⣿⣽⣻⢷⣻⣟⣷⢿⣻⣽⡾⣽⣻⣟⣾⡽⣷⢿⣽⣾⣻⡽⣷⢯⣷⣟⡿⣽⣻⣽⡾⣿⣽⢾⣟⣾⣽⣻⢯⣟⣾⣟⡷⣟⣯⡿⣾⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀
  115.         ⠀⠀⢹⣿⣿⣿⣿⣿⢾⣽⡾⣟⣷⣟⡾⣷⣻⢷⣯⣿⣿⣿⣿⣿⣿⢷⣻⡿⣽⣳⣯⡿⣯⣟⣷⢯⣟⣿⣽⢾⣯⣟⣯⣷⢿⣻⢷⣯⢿⣽⢯⣿⣞⡷⣿⣽⣻⣯⣷⣻⢿⣽⢯⣷⢿⣳⣯⣿⢾⣻⣞⡿⣯⣟⣷⢯⣿⣻⢷⣟⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀
  116.         ⠀⠀⢸⣿⣿⣿⣿⣿⣟⣾⣽⢿⡾⣽⣻⣽⢯⣿⣞⣿⣿⣿⣿⣿⣿⣟⣯⣿⣽⣻⣾⡽⣷⣻⣽⣟⡿⣾⡽⣟⣾⡽⣷⢯⣿⢯⣿⢾⡿⣽⣻⢷⣯⢿⡷⣯⣷⣟⣾⢯⣿⢾⡿⣽⣻⢯⣷⢯⣿⢯⡿⣽⣟⣾⢯⣿⣳⣿⣻⢾⣿⣿⣿⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀
  117.         ⠀⠀⠀⢻⣿⣿⣿⣿⣿⣾⣯⣿⡽⣿⡽⣯⣿⣳⢿⣾⣿⣿⣿⣿⣿⣟⣾⣳⣯⣷⢯⣿⣽⣻⡾⣽⣻⢷⣟⡿⣽⣻⣽⢿⣽⣻⡾⣿⣽⣻⣽⢿⣾⣻⣽⣷⣻⢾⣯⡿⣽⣯⣟⣯⣿⣻⡽⣿⣽⣻⣽⣟⣾⢯⣿⣳⢿⡾⣽⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
  118.         ⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣷⣟⡷⣯⣿⣳⣯⣷⢿⣻⣽⢿⣞⣿⢯⣟⣾⣟⡷⣿⡽⣷⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣾⣿⣷⣿⣾⣿⣾⣿⣿⣿⣿⣿⣿⣟⣾⣟⡷⣿⢯⣟⡿⣾⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀
  119.         ⠀⠀⠀⠀⠀⠈⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢾⣽⣻⣽⡾⣯⣷⢯⣿⣻⢾⣯⢿⣾⣻⢯⣷⣻⣽⡷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣻⢷⣯⣷⣻⣽⣯⢿⣯⣟⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀
  120.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠙⠋⠋⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⣯⡷⣟⣷⢿⣳⣯⣿⣳⡿⣯⣟⡿⣞⣯⣿⣽⣻⡾⣽⣿⣿⣿⣿⣿⡿⠿⠿⠿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣻⢿⣽⣳⣯⣟⡿⣞⣷⣟⡷⣯⣿⢾⣽⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀
  121.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣿⣿⣿⣿⣿⣷⣻⢿⣽⣻⢯⣷⢯⣷⣟⡿⣞⣿⣻⣽⢾⣳⡿⣽⣟⣾⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀  ⢸⣿⣿⣿⣿⣿⡾⣽⣯⡷⣟⣷⣻⣽⣟⡷⣯⣿⣻⢾⣻⣽⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
  122.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢿⣿⣿⣿⣿⣷⣟⣯⣷⢿⣻⡽⣟⣷⣯⢿⣻⢷⣻⣽⣟⣯⢿⣻⡾⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀  ⠘⣿⣿⣿⣿⣿⡿⣽⣞⡿⣯⢿⣽⣞⣯⣿⣽⢾⣻⢿⡽⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
  123.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⣿⣿⣿⣿⣿⣞⡿⣞⡿⣯⣟⣿⢾⣽⣻⢯⣿⢯⣷⢯⣟⣿⣳⡿⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀  ⣿⣿⣿⣿⣿⡿⣽⡾⣿⡽⣿⣞⣯⣷⣟⡾⣟⣯⣿⣻⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  124.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠘⣿⣿⣿⣿⣿⣯⣟⡿⣽⣯⣟⣾⢿⡽⣯⡿⣯⢿⡾⣟⡿⣾⣽⣻⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀  ⢹⣿⣿⣿⣿⣿⢯⣟⣷⢿⣳⣯⣟⣾⣽⣻⢯⣟⣾⣽⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  125.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢿⣿⣿⣿⣿⣷⣻⢿⣽⣞⣯⣟⣯⡿⣷⣟⡿⣯⣟⡿⣽⡷⣯⢿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀  ⢸⣿⣿⣿⣿⣿⢯⣿⢾⣻⣯⢷⡿⣽⣾⣻⢯⣿⣽⣾⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  126.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⣿⣿⣿⣿⣿⡽⣟⣾⢯⣟⣾⢯⣟⣷⣻⣽⣟⣾⣟⣯⣿⡽⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀  ⢸⣿⣿⣿⣿⣿⡿⣽⣻⢷⣻⣯⢿⡷⣯⣟⣿⣳⣯⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  127.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠘⣿⣿⣿⣿⣿⣟⣯⣿⢯⣿⣽⣻⣟⣾⢯⣷⣻⢷⣯⣷⣯⣿⣷⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀ ⠀ ⣿⣿⣿⣿⣿⣿⣽⣯⣿⣻⣾⣿⣽⣟⣾⣽⣷⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  128.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀ ⠀ ⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  129.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠈⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠟⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀  ⠸⠿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⠿⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  130.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠉⠉⠉⠉⠛⠛⠛⠛⠛⠛⠛⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀
  131.  
  132.  
  133.         ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  134. */
  135.  
  136. #include <bits/stdc++.h>
  137.  
  138. // #pragma GCC target ("avx2")
  139. // #pragma GCC optimization ("O3")
  140. // #pragma GCC optimization ("unroll-loops")
  141.  
  142. //  M1nK's Ducky Mask: "Strongest Man In The World"
  143.  
  144. #define task "TASK"
  145.  
  146. #define el '\n'
  147. #define fi first
  148. #define se second
  149. #define pi acos (-1)
  150. #define pb push_back
  151. #define ll long long
  152. #define ld long double
  153. #define pll pair <ll, ll>
  154. #define ull unsigned ll
  155. #define pll2 pair <ll, pll>
  156. #define all(a) a.begin (), a.end ()
  157. #define heap_max(a) priority_queue <a>
  158. #define REP(i, n) for (ll i = 0, _n = (n); i < _n; i++)
  159. #define REPD(i, n) for (ll _n = (n), i = _n - 1; i >= 0; i--)
  160. #define FOR(i, a, b) for (ll i = (a), _b = (b); i <= _b; i++)
  161. #define FOD(i, a, b) for (ll i = (a), _b = (b); i >= _b; i--)
  162. #define heap_min(a) priority_queue <a, vector <a>, greater <a>>
  163. #define FOr(i, a, b, c) for (ll i = (a), _b = (b); i <= _b; i += (c))
  164. #define FOd(i, a, b, c) for (ll i = (a), _b = (b); i >= _b; i -= (c))
  165.  
  166. #define Mirai ios_base:: sync_with_stdio (0);
  167. #define Kuriyama cin.tie (nullptr); cout.tie (nullptr);
  168.  
  169. using namespace std;
  170. const ll INF = 1e18;
  171. const int MOD = 1e9 + 7;
  172. const int minN = 1e3 + 7;
  173. const int maxN = 1e5 + 7;
  174. const int LOG = __lg (maxN) + 1; 
  175.  
  176. template <class X> ll Mask (X s) { return (1LL << s); }
  177. template <class X> ll BitGet (X s, ll i) { return (s >> i) & 1LL; }
  178. template <class X> ll BitCnt (X s) { return __builtin_popcountll (s); }
  179. template <class X, class Y> bool maximize (X &a, Y b) { return (a < b) ? a = b, 1 : 0; }
  180. template <class X, class Y> bool minimize (X &a, Y b) { return (a > b) ? a = b, 1 : 0; }
  181.  
  182. // --------------- M1nK_08 --------------- //
  183.  
  184. ll n, u, v, root, q;
  185.  
  186. ll ans[maxN];
  187.  
  188. vector <ll> adj[maxN];
  189.  
  190. // Segment Tree + Lazy
  191. ll st[maxN << 2], lz[maxN << 2];
  192. void Build (ll id = 1, ll l = 1, ll r = n) {
  193.     if (l == r) {
  194.         st[id] = 1;
  195.         return;
  196.     }
  197.     ll mid = (l + r) >> 1;
  198.     Build (id << 1, l, mid);
  199.     Build (id << 1 | 1, mid + 1, r);
  200. }
  201. void Down (ll id) {
  202.     lz[id << 1] = (lz[id << 1] + lz[id]) % MOD;
  203.     st[id << 1] = (st[id << 1] + lz[id]) % MOD;
  204.     lz[id << 1 | 1] = (lz[id << 1 | 1] + lz[id]) % MOD;
  205.     st[id << 1 | 1] = (st[id << 1 | 1] + lz[id]) % MOD;
  206.     lz[id] = 0;
  207. }
  208. void Upd (ll u, ll v, ll val, ll id = 1, ll l = 1, ll r = n) {
  209.     if (r < u || v < l) return;
  210.     if (u <= l && r <= v) {
  211.         lz[id] = (lz[id] + val) % MOD;
  212.         st[id] = (st[id] + val) % MOD;
  213.         return;
  214.     }
  215.     Down (id);
  216.     ll mid = (l + r) >> 1;
  217.     Upd (u, v, val, id << 1, l, mid);
  218.     Upd (u, v, val, id << 1 | 1, mid + 1, r);
  219.     st[id] = max (st[id << 1], st[id << 1 | 1]);
  220. }
  221. ll Get (ll pos, ll id = 1, ll l = 1, ll r = n) {
  222.     if (r < pos || pos < l) return 0;
  223.     if (l == pos && r == pos) return st[id];
  224.     Down (id);
  225.     ll mid = (l + r) >> 1;
  226.     return max (
  227.         Get (pos, id << 1, l, mid),
  228.         Get (pos, id << 1 | 1, mid + 1, r)
  229.                );
  230. }
  231.  
  232. // DFS / HLD / UpdPath
  233. ll sz[maxN], par[maxN], h[maxN], hv[maxN];
  234. void DFS (ll u, ll p) {
  235.     sz[u] = 1;
  236.     for (auto v: adj[u]) {
  237.         if (v == p) continue;
  238.         par[v] = u;
  239.         h[v] = h[u] + 1;
  240.         DFS (v, u);
  241.         sz[u] += sz[v];
  242.         if (sz[v] > sz[hv[u]]) hv[u] = v;
  243.     }
  244. }
  245. ll curpos;
  246. ll ID[maxN], pos[maxN];
  247. void HLD (ll u, ll p) {
  248.     ID[u] = p;
  249.     pos[u] = ++curpos;
  250.     if (!!hv[u]) HLD (hv[u], p);
  251.     for (auto v: adj[u]) if (v != par[u] && v != hv[u]) HLD (v, v);
  252. }
  253. void UpdPath (ll u, ll v, ll x) {
  254.     while (ID[u] != ID[v]) {
  255.         if (h[ID[u]] < h[ID[v]]) swap (u, v);
  256.         Upd (pos[ID[u]], pos[u], x);
  257.         u = par[ID[u]];
  258.     }
  259.     Upd (min (pos[u], pos[v]), max (pos[u], pos[v]), x);
  260. }
  261.  
  262. void INIT () {
  263.     cin >> n;
  264.     FOR (u, 1, n) {
  265.         cin >> v;
  266.         if (!v) root = u;
  267.         else {
  268.             adj[u].pb (v);
  269.             adj[v].pb (u);
  270.         }
  271.     }
  272. }
  273. void Solve () {
  274.     INIT ();
  275.  
  276.     DFS (root, -1);
  277.     HLD (root, root);
  278.     Build ();
  279.     FOR (i, 1, n) {
  280.         cin >> u;
  281.         ans[u] = Get (pos[u]);
  282.         if (par[u]) UpdPath (root, par[u], ans[u]);
  283.     }
  284.     FOR (i, 1, n) cout << ans[i] % MOD << ' ';
  285. }
  286.  
  287. signed main (void) {
  288.     Mirai Kuriyama;
  289.     if (fopen (task".INP", "r")) {
  290.         freopen (task".INP", "r", stdin);
  291.         freopen (task".OUT", "w", stdout);
  292.     }   
  293.     int t = 1; 
  294.     // cin >> t;
  295.     while (t--) Solve ();
  296.     return 0;
  297. }
  298.  
Success #stdin #stdout 0.01s 13832KB
comments (?)
stdin 
6
2 3 0 5 3 5
1 4 6 5 2 3
stdout 
1 2 9 1 3 1
https://ideone.com/lgmeCR
language:
C++14 (gcc 8.3)
created:
158 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!