Comment 1 for bug 1943488

I am facing the exact same error in the exact same configuration

$ lsb_release -rd
Description: Ubuntu 20.04.3 LTS
Release: 20.04

$ apt-cache policy nautilus
nautilus:
  Installed: 1:3.36.3-0ubuntu1
  Candidate: 1:3.36.3-0ubuntu1
  Version table:
 *** 1:3.36.3-0ubuntu1 500
        500 http://us.archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages
        100 /var/lib/dpkg/status
     1:3.36.1.1-1ubuntu2 500
        500 http://us.archive.ubuntu.com/ubuntu focal/main amd64 Packages

@perebal-sze, thank you for sharing about cutting and pasting the search text in step 4. I hadn't know it before. It works for me as well.