Facebook Messanger. Invalid token

I'm a page admin and trying to debug messanger bot. Recently, I've changed the password and now when I try to reply to myself in messager via API I get an error

{
  "error": {
    "message": "Error validating access token: The session has been invalidated because the user changed their password or Facebook has changed the session for security reasons.",
    "type": "OAuthException",
    "code": 190,
    "error_subcode": 460
  }
}

The thing is I don't have an access token, to begin with, the doc says

To send messages to someone on Messenger, the conversation must be initiated by the user.

It also says

Apps in Development Mode, are restricted to message people that have a role in the app.

I've tried to

Recreate page token
Block/Unblock page and delete conversion
Tried to remove myself from admins, but that's impossible since I'm the only admin

The only option I see left is to remove the app altogether and create a new one, but that doesn't seem like a good solution

Solution

This has nothing to do with the fact that the user needs to message your page first, before the bot can respond.

Your bot needs a page token to perform its actions, and according to the error message, the one you have been using, had expired.

So the token you got set in your bot configuration needs to be replaced with a fresh, valid one.